同上

1 #include
     
       2 #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 }