同上
1 #include2 #include 3 #define N 1000005 4 #define LL long long 5 #define inf 0x3f3f3f3f 6 using namespace std; 7 inline int ra() 8 { 9 int x=0,f=1; char ch=getchar();10 while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar();}11 while (ch>='0' && ch<='9') {x=x*10+ch-'0'; ch=getchar();}12 return x*f;13 }14 int n,cas,fail[N];15 char ch[N];16 int main()17 {18 while (scanf("%d",&n))19 {20 if (!n) break;21 scanf("%s",ch+1);22 int fix=0;23 for (int i=2; i<=n; i++)24 {25 while (ch[i]!=ch[fix+1] && fix) fix=fail[fix];26 if (ch[fix+1]==ch[i]) fix++; fail[i]=fix;27 }28 printf("Test case #%d\n",++cas);29 for (int i=2; i<=n; i++)30 {31 int x=i-fail[i];32 if (i%x || x==i) continue;33 printf("%d %d\n",i,i/x);34 }35 printf("\n");36 }37 return 0;38 }