poj2406字符串的级联

题目链接：power string

题目描述(Description)

给一个字符串，求出其最大的循环子串。

比如：

输入：
    abcd
    aaaa
    ababab
    ababcab
输出：
    1
    4
    3
    1

分析(Analysis)

• 直接用KMP的next数组求，然后计算循环节的长度

• 注意给出的第四种情况，虽然有循环前缀abab，但后面的字符串不是循环形式，所以输出结果还是1.

代码(Code)

#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=1000001;
char s[maxn];
int next[maxn];
int len;
void get_next()
{
    next[0]=-1;
    int j=0,k=-1;
    while(j<len)
    {
        if(k==-1||s[j]==s[k])
            next[++j]=++k;
        else
            k=next[k];
    }
}
int main()
{
    while(scanf("%s",s)&&s[0]!='.')
    {
        memset(next,0,sizeof(next));
        len=strlen(s);
        get_next();
        int length=len-next[len];
        if(length!=len&&(len%length)==0)
            printf("%d\n",len/length);
        else
            printf("1\n");
    }
    return 0;
}