[poj2406]Power Strings(KMP循环节)

题意：给定一个字符串，让你求出他最多由几个相同的连续子串连接而成。

解题关键：根据KMP的next函数的性质，已知字符串t第K个字符的next[k],那么d=k-next[k],如果k%d==0,那么t[1……k]最多可均匀的分成k/d份。也就是可以生成一个长度为d的重复度为k/d的字串。（这里脑子抽了可以画图理解

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #include<cstdlib>
 5 #include<cmath>
 6 #include<iostream>
 7 #define N 1000002
 8 using namespace std;
 9 typedef long long ll;
10 int Next[N];
11 char s[N],t[N];
12 int slen,tlen;
13 int n,m;
14 int num=0,num1=0,num2=0;
15 void getNext(){
16     tlen=strlen(t);
17     int i=0,j=-1;
18     Next[0]=-1;
19     while(i<tlen){
20         if(j==-1||t[i]==t[j]) Next[++i]=++j;
21         else j=Next[j];
22     }
23 } 
24 
25 int main(){
26     while(scanf("%s",t)&&(t[0]!='.')){
27         getNext();
28         if(tlen%(tlen-Next[tlen])){
29             printf("1
");
30         }
31         else{
32             printf("%d
",tlen/(tlen-Next[tlen]));
33         }
34     }
35     return 0;
36 }