hdu3746Cyclic Nacklace（KMP）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3746

用到KMP的nex数组。

len-nex[len]是循环节长度。

 1 #include<cstdio>
 2 #include<cstring>
 3 char p[100010];
 4 int nex[100010];
 5 int main()
 6 {
 7     int t;
 8     scanf("%d",&t);
 9     while(t--)
10     {
11         scanf("%s",p);
12         int len=strlen(p);
13         int i=0,k=-1;
14         nex[0]=-1;
15         while(i<len)
16         {
17             if(k==-1||p[i]==p[k])
18                 nex[++i]=++k;
19             else k=nex[k];
20         }
21        int l=len-nex[len];//循环节长度
22        if(l!=len&&len%l==0) puts("0");
23        else printf("%d
",l-nex[len]%l);
24     }
25 }