KMP_最小循环节

最小循环节
KMP，next表示模式串如果第i位(设str[0]为第0位)与文本串第j位不匹配则要回到第next[i]位继续与文本串第j位匹配。则模式串第1位到next[n]与模式串第n-next[n]位到n位是匹配的。所以思路和上面一样，如果n%（n-next[n]）==0,则存在重复连续子串，长度为n-next[n]。
http://poj.org/problem?id=2406

#include<stdio.h>
#include <string.h>
using namespace std;
int next[1000005];
char p[1000005];
int pLen;
void getNext()
{
    next[0] = -1;
    int k = -1;
    int j = 0;
    while (j <=pLen-1)
    {
        if (k == -1 || p[j] == p[k])
        {
            ++k;
            ++j;
            next[j] = k;
        }
        else
        {
            k = next[k];
        }
    }
}
int main()
{
  while(scanf("%s",p)!=EOF)
    {
        if(p[0]=='.')
            break;
        pLen=strlen(p);
        getNext();
        if(pLen%(pLen-next[pLen])==0)
            printf("%d\n",pLen/(pLen-next[pLen]));
        else
            printf("1\n");
    }
    return 0;
}