被打哭了......神特么kmp,还能这么用!看来我理解的还不够透彻,这里最神奇的就是只有相同的字串才能往下延伸,而"i-f[i]"就正好是前面空出来的模板块,也就是f[i]中不计数的那块,而字符串都是从0开始的,对应的往下加一个却正好成立构成倍数关系
#include#include #include #include using namespace std;const int maxn=1000000+100;int f[maxn];string p;int n;int main(){ int kase=0; while(~scanf("%d",&n)&&n) { kase++; cin >> p; f[0]=0,f[1]=0; for(int i=1; i 0&&i%(i-f[i])==0) { printf("%d %d\n",i,i/(i-f[i])); } printf("\n"); } return 0;}
,很神奇,这是什么,规律?