题意：给两个字符串 S 和 T ，让找一个最长的字符串 P 使得 P 是 S 的前缀且是 T 的后缀。
思路：考虑 KMP 算法中的 Next 数组即为所求。只需要在 S 和 T 之间用一个无效的字符连接起来，求其 Next 数组，Next[len] 即为答案。
推荐学习链接：
1 #include <iostream> 2 #include <stdio.h> 3 #include <stdlib.h> 4 #include <cstring> 5 #include <algorithm> 6 using namespace std ; 7 8 void nnnxt(char s[],int nxt[]) 9 { 10 memset(nxt,0,sizeof(nxt)) ; 11 int i = 0 , j = -1 , len = strlen(s) ; 12 nxt[0] = -1 ; 13 while (i < len) { 14 while (j != -1 && s[i] != s[j]) j = nxt[j] ; 15 nxt[++i] = ++ j ; 16 } 17 } 18 19 char s[100010] , t[50010] ; 20 int nxt[100010] ; 21 22 int main() 23 { 24 freopen("1.in","r",stdin) ; 25 //freopen("hehe.out","w",stdout) ; 26 while (~scanf("%s%s",s,t)) { 27 strcat(s,"#") ; 28 strcat(s,t) ; 29 nnnxt(s,nxt) ; 30 printf("%d\n",nxt[strlen(s)]) ; 31 } 32 return 0 ; 33 }
~end~~_~
原文：http://www.cnblogs.com/chdacm/p/5395046.html
