http://acm.split.hdu.edu.cn/showproblem.php?pid=5782
题意：
给出两个长度相等的字符串，输出两个字符的每个前缀是否循环相同。
思路：
如果连个串循环相同的话，那一定可以找到一个位置，使得第一个串的前缀等于另一个串的后缀。这样的话其实就是扩展kmp的思想，kmp处理，然后用哈希来比较两段字符是否相等。
1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 #include<cstdio> 5 #include<vector> 6 #include<stack> 7 #include<queue> 8 #include<cmath> 9 #include<map> 10 #include<set> 11 using namespace std; 12 typedef long long ll; 13 typedef pair<int,int> pll; 14 const int INF = 0x3f3f3f3f; 15 const int maxn = 10000 + 5; 16 17 const int seed =31; 18 19 int n; 20 int ans[maxn]; 21 int f[maxn]; 22 ll base[maxn]; 23 ll Hash[2][maxn]; 24 char s1[maxn],s2[maxn]; 25 26 int check(int flag, int l, int r) 27 { 28 if(l-1==r) return 1; 29 int L=r-l+1; 30 ll tmp1 = Hash[flag][l]-Hash[flag][l+L]*base[L]; 31 ll tmp2 = Hash[!flag][0]-Hash[!flag][0+L]*base[L]; 32 return tmp1==tmp2; 33 } 34 35 36 void kmp(char* T, char* P, int flag) 37 { 38 f[0]=0; f[1]=0; 39 for(int i=1;i<n;i++) 40 { 41 int j=f[i]; 42 while(j && P[i]!=P[j]) j=f[j]; 43 f[i+1]= P[i]==P[j]?j+1:0; 44 } 45 46 int j=0; 47 for(int i=0;i<n;i++) 48 { 49 while(j && P[j]!=T[i]) j=f[j]; 50 if(P[j]==T[i]) 51 { 52 j++; 53 if(!ans[i]) ans[i]=check(flag,j,i); 54 } 55 } 56 } 57 58 int main() 59 { 60 //freopen("in.txt","r",stdin); 61 base[0]=1; 62 for(int i=1;i<=maxn;i++) base[i]=base[i-1]*seed; 63 64 while(~scanf("%s%s",s1,s2)) 65 { 66 memset(ans,0,sizeof(ans)); 67 n=strlen(s1); 68 Hash[0][n]=Hash[1][n]=0; 69 for(int i=n-1;i>=0;i--) 70 { 71 Hash[0][i]=Hash[0][i+1]*seed+(s1[i]-'a'+1); 72 Hash[1][i]=Hash[1][i+1]*seed+(s2[i]-'a'+1); 73 } 74 kmp(s1,s2,1); 75 kmp(s2,s1,0); 76 for(int i=0;i<n;i++) printf("%d",ans[i]); 77 puts(""); 78 } 79 return 0; 80 }