题意：给你两个字符串，为你第一个字符串的前缀等于第二个字符串的后缀的最大长度是多少
解题思路：KMP，两次匹配，不过方法比较巧妙，两次分开求next就行
解题代码：
1 // File Name: getnext.cpp 2 // Author: darkdream 3 // Created Time: 2014年09月09日 星期二 22时35分02秒 4 5 #include<vector> 6 #include<list> 7 #include<map> 8 #include<set> 9 #include<deque> 10 #include<stack> 11 #include<bitset> 12 #include<algorithm> 13 #include<functional> 14 #include<numeric> 15 #include<utility> 16 #include<sstream> 17 #include<iostream> 18 #include<iomanip> 19 #include<cstdio> 20 #include<cmath> 21 #include<cstdlib> 22 #include<cstring> 23 #include<ctime> 24 #define LL long long 25 26 using namespace std; 27 char str[50005]; 28 char str1[50005]; 29 int next[50005]; 30 int next1[50005]; 31 void getnext() 32 { 33 int len = strlen(str); 34 int len1 = strlen(str1); 35 next[0] = -1; 36 int k = -1; 37 int j = 0 ; 38 int sum = 0 ; 39 while(j <= len - 1 ) 40 { 41 if(k == -1 || str[j] == str[k]) 42 { 43 ++j; 44 ++k; 45 next[j] = k ; 46 } 47 else { 48 k = next[k]; 49 } 50 } 51 k = 0; 52 j = 0 ; 53 while(j <= len1 -1) 54 { 55 if(k == -1 || str[k] == str1[j]) 56 { 57 ++ j ; 58 ++ k ; 59 next1[j] = k; 60 }else{ 61 k = next[k]; 62 } 63 } 64 /*for(int i = 0 ;i <= len1 ;i ++) 65 printf("%d ",next1[i]); 66 printf(" ");*/ 67 if(next1[len1] == 0) 68 printf("0 "); 69 else{ 70 for(int i = 0 ;i < next1[len1] ;i ++) 71 printf("%c",str[i]); 72 printf(" %d ",next1[len1]); 73 } 74 } 75 int main(){ 76 while(scanf("%s",str) != EOF) 77 { 78 scanf("%s",str1); 79 getnext(); 80 } 81 return 0; 82 }