经典扩展kmp。
1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 using namespace std; 5 6 void getA (char *T,int *A){ 7 int j=0; 8 int len=strlen (T); 9 while(1+j<len&&T[0+j]==T[1+j]) 10 j = j + 1; 11 A[1]=j; 12 int k=1; 13 for(int i=2; i<len; i++){ 14 int Len = k + A[k] - 1,L = A[i-k]; 15 if( L < Len - i + 1 ) 16 A[i] = L; 17 else{ 18 j = max(0,Len -i +1); 19 while(i+j<len&&T[i+j] == T[0+j]) 20 j = j + 1; 21 A[i] = j,k = i; 22 } 23 } 24 } 25 26 void getB (char *S,char *T,int *A,int *B){ 27 getA (T,A); 28 int j = 0; 29 int lens=strlen (S); 30 int lent=strlen (T); 31 while(j<lens&&j<lent&&T[0+j]==S[0+j]) 32 j = j + 1; 33 B[0] = j; 34 int k = 0; 35 for(int i=1; i<lens; i++) { 36 int Len = k + B[k] - 1,L = A[i-k]; 37 if( L < Len - i + 1 ) 38 B[i] = L; 39 else { 40 j = max(0,Len -i +1); 41 while(i+j<lens&&j<lent&&S[i+j] == T[0+j]) 42 j = j + 1; 43 B[i] = j,k = i; 44 } 45 } 46 } 47 48 char S[200000],T[200000]; 49 int A[200000],B[200000]; 50 int main (){ 51 while (~scanf ("%s %s",S,T)){ 52 getB (T,S,A,B); 53 int lent=strlen(T); 54 int ans=0; 55 for (int i=0;i<lent;i++){ 56 if (i+B[i]==lent){ 57 ans=B[i]; 58 break ; 59 } 60 //cout<<B[i]<<" "; 61 } 62 if (ans){ 63 for (int i=0;i<ans;i++) 64 printf ("%c",S[i]); 65 printf (" "); 66 } 67 cout<<ans<<endl; 68 } 69 return 0; 70 }