信息学奥赛一本通T1457-Power Strings【KMP】

信息学奥赛一本通T1457-Power Strings - C语言网 (dotcpp.com)

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N=1e6+100;
char str[N];
int nex[N];
int res=0;
signed main()
{
    while(scanf("%s",str+1)!=EOF)
    {
        if(str[1]=='.')
            break;
        memset(nex,0,sizeof(nex));
        int len=strlen(str+1);
        for(int i=2,j=0;i<=len;i++)
        {
            while(j&&str[i]!=str[j+1])
                j=nex[j];
            if(str[i]==str[j+1])
                j++;
            nex[i]=j;
        }
        if(len%(len-nex[len])==0)
        {
            res=len/(len-nex[len]);
            printf("%d\n",res);
        }
        else
            printf("1\n");
    }
    return 0;
}