题目链接：点击查看

题目大意：给出一个长度为n的字符串，问有哪些前缀是周期性字符串

题目分析：因为n给的很大，所以肯定不能暴力判断了，我们可以巧妙的利用kmp的next数组进行判断，next数组有一个挺重要的性质：

n-next[n]是在当前n位置时的长度最小循环节长度

有了上述结论，在跑出next数组后，就不难判断当前的前缀是否属于周期性字符串了，也算是一个模板题了

代码：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> #include<unordered_map> using namespace std; typedef long long LL; const int inf=0x3f3f3f3f; const int N=1e6+100; char s[N]; int nx[N]; void getnext()//求next数组 { nx[0]=-1; int i=0,j=-1; int len=strlen(s); while(i<len) { if(j==-1||s[i]==s[j]) nx[++i]=++j; else j=nx[j]; } } int main() { // freopen("input.txt","r",stdin); int n; int kase=0; while(scanf("%d",&n)!=EOF&&n) { scanf("%s",s); getnext(); printf("Test case #%d\n",++kase); for(int i=2;i<=n;i++) { int len=i-nx[i]; if(len!=0&&i%len==0&&i/len>1) printf("%d %d\n",i,i/len); } printf("\n"); } return 0; }