poj 2406 Power Strings(KMP)

题意：给一个字符串，求这个字符串能由一个子串最多组成多少次。。

next_val匹配

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 using namespace std;
 5 
 6 char t[1000005];
 7 int len_t,nev[1000005];
 8 int get_nextv()
 9 {
10     int i=0,j=-1,x;
11     nev[0]=-1;
12     while(i<len_t)    //刚开始一直纠结为什么不是len_t减1，，后来想了想是要把后面的那一个也要比较一下看是否相同。。。
13     {
14         if(j==-1||t[i]==t[j])
15         {
16         ++i; ++j;
17         if(t[i]!=t[j])
18         nev[i]=j;
19         else
20         nev[i]=nev[j];
21         }
22         else
23         j=nev[j];
24     }
25     x=len_t-j;
26     if(len_t%x==0)
27     return len_t/x;
28     else
29     return 1;
30 }
31 int main()
32 {
33     while(~scanf("%s",t)&&strcmp(t,".")!=0)
34     {
35         len_t=strlen(t);
36         cout<<get_nextv()<<endl;
37     }
38     return 0;
39 }

next匹配

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 using namespace std;
 5 
 6 char t[1000005];
 7 int len_t,ne[1000005];
 8 int get_next()
 9 {
10     int i=0,j=-1,x;
11     ne[0]=-1;
12     while(i<len_t)
13     {
14         if(j==-1||t[i]==t[j])
15         {
16         ++i; ++j;
17         ne[i]=j;
18         }
19         else
20         j=ne[j];
21     }
22     x=len_t-j;
23     if(len_t%x==0)
24     return len_t/x;
25     else
26     return 1;
27 }
28 int main()
29 {
30     while(~scanf("%s",t)&&strcmp(t,".")!=0)
31     {
32         len_t=strlen(t);
33         cout<<get_nextv()<<endl;
34     }
35     return 0;
36 }