开始补坑。
kmp中的fail数组fail[i]是指“当模式串的i位置匹配失败时，应该再用模式串的fail[i]位置匹配“
1 #include <cstdio> 2 #include <cstring> 3 #define maxn 100010 4 5 char aa[maxn*2], bb[maxn], cc[maxn]; 6 int f[maxn]; 7 8 void getfail( char *P, int *f ) { 9 int n = strlen(P); 10 f[0] = f[1] = 0; 11 for( int i=1; i<n; i++ ) { 12 int j=f[i]; 13 while( j && P[j]!=P[i] ) j=f[j]; 14 f[i+1] = P[j]==P[i] ? j+1 : 0; 15 } 16 } 17 bool kmp( char *T, char *P, int *f ) { 18 int n=strlen(T), m=strlen(P); 19 for( int i=0,j=0; i<n; i++ ) { 20 while( j && T[i]!=P[j] ) j=f[j]; 21 if( T[i]==P[j] ) j++; 22 if( j==m ) return true; 23 } 24 return false; 25 } 26 27 int main() { 28 while( scanf("%s%s",cc,bb)==2 ) { 29 aa[0] = 0; 30 strcat(aa,cc); 31 strcat(aa,cc); 32 getfail(bb,f); 33 printf( "%s ", kmp(aa,bb,f) ? "yes" : "no" ); 34 } 35 }