HDU 2594(求最长公共前后缀 kmp)

题意是在所给的两个字符串中找最长的公共前后缀，即第一个字符串前缀和第二个字符串后缀的最长相等串。

思路是将两个字符串拼接在一起，然后直接套用 kmp 算法即可。

要注意用 next 会报编译错误，改成 Next 才过……但 next 确实不是 c++ 关键字。

代码如下：

1 1 #include <iostream>
2 2 #include <cstring>
3 3 #include <cstdio>
4 4 using namespace std;
5 5 const int N=50000+5;
6 6 char a[N*2],b[N];
7 7 int Next[N*2];
8 8 void getNext()
9 9 {
1010     Next[0] = -1;
1111     int i=1,j=0,len=strlen(a);
1212     while(i<len)
1313     {
1414         if(j==-1||a[i]==a[j])
1515         {
1616             i++;j++;
1717             Next[i]=j;
1818         }
1919         else
2020             j=Next[j];
2121     }
2222 }
2323 int main()
2424 {
2525     while(~scanf("%s%s",a,b))
2626     {
2727         int lena=strlen(a),lenb=strlen(b);
2828         strcat(a,b);//将b字符串连在a字符串后
2929         getNext();//求解Next数组
3030         int ans=Next[strlen(a)];
3131         while(ans>lenb||ans>lena) ans=Next[ans];
3232         if(ans==0) puts("0");
3333         else
3434         {
3535             a[ans] = 0;
3636             printf("%s %d\n",a,ans);
3737         }
3838     }
3939     return 0;
4040 }

View Code