假设s可以由t重复k次拼成，即s=tttt……tt，我们称为s=t^k。先给定一个字符串s，求最大的n使得存在t满足s=t^n。
用kmp的nxt数组解决~
#include<cstdio> #include<cstring> #include<iostream> using namespace std; const int maxn=1e7+14; char str[maxn]; int nxt[maxn]; int len; void getNext () { int j,k; j=0; k=-1; nxt[0]=-1; while (j<len) { if (k==-1||str[j]==str[k]) nxt[++j]=++k; else k=nxt[k]; } } int main () { while (~scanf("%s",str)) { if (strcmp(str,".")==0) break; len=strlen(str); getNext(); if (len%(len-nxt[len])==0&&len/(len-nxt[len])>1) printf ("%d\n",len/(len-nxt[len])); else printf ("1\n"); } return 0; }
原文：https://www.cnblogs.com/zhanglichen/p/12332706.html