Power Strings----poj2406(kmp扩展 循环节)

题目链接：http://poj.org/problem?id=2406

题意：就是求串s能够最多由多少个相同的串a串联而成；

例如 ababab 由3个ab串联而成；

abababa 只能由1个abababa组成；

kmp中的Next[n]（下标从0开始）表示n个元素的前缀和后缀的最大匹配；

  a b a b a b a b

　0 1 2 3 4 5 6 7

0-5和2-7是最大匹配Next【n】= 6；ab就是循环节（因为n/(n-next[n])是整数，所以是循环节）即 n - Next【n】；

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;

#define N 1000010

char s[N];
int Next[N], n;

void Getnext()
{
    int i = 0, j = -1;
    Next[0] = -1;
    while(i<n)
    {
        if(j==-1 || s[i] == s[j])
            Next[++i] = ++j;
        else
            j=Next[j];
    }
}

int main()
{
    while(scanf("%s", s),s[0]!='.')
    {
        n = strlen(s);

        Getnext();

        int ans = n-Next[n];

        if(n%ans!=0)
            ans = 1;
        else
            ans = n/ans;
        printf("%d
", ans);
    }
    return 0;
}
/*
aabaabaa
1
*/