初学KMP Power Strings hoj

[cpp]
/*该段话为转载,很精确.

大致题意：
    给出一个字符串，求出这个字符串最多能够由多少个子串首尾连接而成。比如“ababab”就是由3个“ab”相连而成，所以输出3，“abcdef”只能看作一个“abcdef”所以输出1。

大致思路：

    KMP中next数组的巧妙运用。在这里我们假设这个字符串的长度是len，那么如果len可以被len-next[len]整除的话，我们就可以说len-next[len]就是那个最短子串的长度

    为什么呢？假设我们有一个字符串ababab,那么next[6]=4对吧，由于next的性质是，匹配失败后，下一个能继续进行匹配的位置，也就是说，把字符串的前四个字母，abab,平移2个单位，这个abab一定与原串的abab重合（否则就不满足失败函数的性质），这说明了什么呢，由于字符串进行了整体平移，而平移后又要重叠，那么必有

s[1]=s[3],s[2]=s[4],s[3]=s[5],s[4]=s[6].说明长度为2的字符串在原串中一定重复出现，这就是len-next[len]的含义！*/

#include <cstring>
#include <stdio.h>

const int maxn=1000005;
int next[maxn];
void ready(char *mode,int lenb)
{
    next[0]=-1;
    int j=-1;
    for(int i=1; i<lenb; i++)
    {
        while(j>-1&&mode[j+1]!=mode[i]) j=next[j];
        if(mode[j+1]==mode[i]) j++;
        next[i]=j;
    }
}
int main()
{
    char mode[maxn];
    while(scanf("%s",mode)!=EOF&&strcmp(mode,".")!=0)
    {
        int len=strlen(mode);
        ready(mode,len);
        int m=len-1-next[len-1];
        if(len%m==0) printf("%d\n",len/m);
        else printf("1\n");
    }
    return 0;
}

作者：ehi11

补充：软件开发 , C++ ,