HDU3746 Cyclic Nacklace KMP

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 5 #include<cmath>
 6 #include<queue>
 7 using namespace std;
 8 const int maxn=1000010;
 9 const double eps=1e-8;
10 const long long modn=1000;
11 char a[maxn]={};
12 int nex[maxn]={};
13 int n;
14 int doit(){
15     int i=0,j=-1;nex[0]=-1;
16     while(i<n){
17         if(j==-1||a[j]==a[i]){
18             nex[++i]=++j;
19         }else{
20             j=nex[j];
21         }
22     }
23     int z=n-nex[n];
24     if(nex[n]==0){
25         return n;
26     }else if(n%z==0){
27         return 0;
28     }
29     else {
30         return z-n%z;
31     }
32 }
33 int main(){
34     int T;
35     scanf("%d",&T);
36     while(T-->0){
37         scanf("%s",&a);
38         n=strlen(a);
39         printf("%d
",doit());
40     }
41     return 0;
42 }