#include<cstdio> const int MAXN=1000000+10; char p[MAXN]; int f[MAXN]; void getfail(const int &n) { f[0]=f[1]=0; for(int i=1;i<n;i++) { int j=f[i]; while(j > 0 && p[i]!=p[j]) j=f[j]; if(p[i]==p[j]) j++; f[i+1]=j; } } int main() { int n; int kase=1; while(scanf("%d",&n),n) { scanf("%s",p); getfail(n); printf("Test case #%d\n",kase++); /* for(int i=0;i<n;i++) printf("%d ",f[i]); printf("\n"); */ for(int i=0;i<=n;i++) { if(f[i] >0 && i%(i-f[i])==0) printf("%d %d\n",i,i/(i-f[i])); } printf("\n"); } } |
Double click to view unformatted code.