杭州网站建设专家/app开发工具

图片加载可能有点慢，请跳过题面先看题解，谢谢

然而并不知道 \(KMP\) 为啥会出现在数据结构的章节里。。。
我只想说，这道题还要有多水。。。
对于一个存在最小循环节的位置 \(i\)，满足 \(nxt[i]>0\) 并且 \(i\ mod\ (i-nxt[i]+1)=0\)，然后你就做完了
$
$

//made by Hero_of_Someone
#include<iostream>
#include<cstdio>
#include<cstdlib>
#define il inline
#define RG register
using namespace std;char s[1000010];
int t,n,nxt[1000010];il void init(){scanf("%s",s);for(int i=1;i<n;i++){ int j=nxt[i];while(j && s[j]!=s[i]) j=nxt[j];nxt[i+1]=(s[j]==s[i])?j+1:0;}
}il void work(){printf("Test case #%d\n",++t);for(int i=2;i<=n;i++){if(!nxt[i]) continue;if(i%(i-nxt[i])) continue;printf("%d %d\n",i,i/(i-nxt[i]));}puts("");
}int main(){ while(scanf("%d",&n)&&n){ init(); work(); } return 0; }