文档介绍：九野的博客
ACM 今天你AC了吗? 欢迎acmer讨论~ 群号:126270450
HDU 1867 KMP 求最大尾部重叠
分类: KMP 2013-12-16 19:54 156人阅读评论(0) 收藏举报
题意:
给定2个字符串,a-b 或 b-a
尾部相同部分只输出一次
求长度最小的字符串(长度相同则字典序最小)
#include<>
#include<>
#include<iostream>
#include<algorithm>
using namespace std;
#define N 200050
int f1[N], f2[N];
char s1[N], s2[N];
void getFail(int *f, char *s){
int i, j, len = strlen(s);
j = f[0] = -1;
i = 0;
while(i < len)
{
while(j!=-1 && s[i] != s[j])j = f[j];
i++, j++;
if(s[i] != s[j])f[i] = j;
else f[i] = f[j];
}
}
int KMP(int *f, char *S1, char *S2){
int pos = 0, len = strlen(S1), j = 0, i = 0;
while(i <= len)
{
while(j!=-1 && S1[i] != S2[j]) j = f[j];
i++, j++;
if(i == len)pos = max(pos, j);
}
return pos;
}
void go(char *S1, char *S2, int pos){
int i = strlen(S1);
while(S2[pos])
S1[i++] = S2[pos++];
S1[i] = '\0';
}
char tmp1[N], tmp2[N], as1[N], as2[N];
int main(){
while(~scanf("%s %s", s1, s2)){
getFail(f1, s1);
getFail(f2, s2);
int ans1 = KMP(f2, s1, s2), ans2 = KMP(f1, s2, s1);
1
if(ans1>ans2)
{
go(s1, s2, ans1);
printf("%s\n",s1);
}
else if(ans1<ans2)
{
go(s2, s1, ans2);
printf("%s\n",s2);
}
else
{
memcpy(tmp1, s1, sizeof(s1));
memcpy(tmp2, s2, sizeof(s1));
go(tmp1, tmp2, ans1);
memcpy(as1, tmp1, sizeof(as1));
memcpy(tmp1, s1, sizeof(s1));
memcpy(tmp2, s2, sizeof(s1));
g