kmpnext数组理解循环节 HDU3746

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 
 5 using namespace std;
 6 
 7 int n;
 8 int next1[100010];
 9 char s[100010];
10 
11 void getnext()
12 {
13     int i=0;
14     int j=-1;
15     next1[0]=-1;
16     while(i<n)
17     {
18         while(j!=-1&&s[i]!=s[j])
19         {
20             j=next1[j];
21         }
22         next1[++i]=++j;
23     }
24 }
25 
26 int main()
27 {
28     int T;
29     scanf("%d",&T);
30     while(T--)
31     {
32         scanf("%s",&s);
33         n=strlen(s);
34         getnext();
35         int jie=n-next1[n];
36         int ans=jie-next1[n];
37         //if(ans<0)
38         //    ans=0;
39         if(ans!=jie)
40             cout<<(ans%jie+jie)%jie<<endl;
41         else
42             cout<<ans<<endl;
43     }
44     return 0;
45 }
View Code