hdu 3746 kmp求循环节

 1 #include<stdio.h>
 2 #include<iostream>
 3 #include<string.h>
 4 #include<algorithm>
 5 using namespace std;
 6 const int MAXN=100010;
 7 char str[MAXN];
 8 int next[MAXN];
 9 
10 void getNext(char *p)
11 {
12     int j,k;
13     j=0;
14     k=-1;
15     int len=strlen(p);
16     next[0]=-1;
17     while(j<len)
18     {
19         if(k==-1||p[j]==p[k])
20         {
21             j++;
22             k++;
23             next[j]=k;
24         }
25         else k=next[k];
26     }
27 }
28 int main()
29 {
30     int T;
31     scanf("%d",&T);
32     while(T--)
33     {
34         scanf("%s",&str);
35         getNext(str);
36         int len=strlen(str);
37         if(next[len]==0)
38         {
39             printf("%d
",len);
40             continue;
41         }
42         int t=len-next[len];
43         if(len%t==0)printf("0
");
44         else
45         {
46             printf("%d
",t-len%t);
47         }
48     }
49     return 0;
50 }