poj 2406 Power Strings (KMP+最小循环节)

题目链接: poj 2406

题目大意: 给出一个由某个串重复有限次得到的字符串

求重复次数最多是多少，既找出最小重复子串

解题思路: 字符串abcabcabc的next[ ]值为
0 1 2 3 4 5 6 7 8 9
a b c a b c a b c
-1 0 0 0 1 2 3 4 5 6
假设主串为abcabcabcX，模式串为abcabcabcK，Kmp的匹配过程
匹配到第10个字符发现不符:
a b c a b c a b c X
a b c a b c a b c K
不符合，j=next[j]
a b c a b c a b c X
a b c a b c a b c K
不符合，j=next[j]
a b c a b c a b c X
a b c a b c a b c K;

由next数组的定义可得： S[0-2]=S[3-5]=S[6-8]

当且仅当len%(len-next[len])=0时,len-next[len]是字符串的最小循环节

代码:

#include <stdio.h>#include <string.h>#define MAX 1000005char ch[MAX];int next[MAX];int Get_next(int Tlen){int i=0,j=-1;next[0]=-1;while(i<Tlen){if(j==-1||ch[i]==ch[j]){i++; j++;next[i]=j;}elsej=next[j];}i=Tlen-j;        //**if(Tlen%i==0)          //**return Tlen/i; //**return 1;}int main(){int Tlen;while(scanf("%s",ch)!=EOF){if(ch[0]=='.')break;Tlen=strlen(ch);printf("%d\n",Get_next(Tlen));}return 0;}