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 1000005
char 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;
		}
		else
			j=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;
}