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

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;}