acwing 141. 周期

#include<iostream>
#include<algorithm>
#include<cstring>
 
using namespace std ;
const int N = 1e6 +10 ;
int n , m ;
char s[N] ;
int ne[N] ;
void get_ne(){
  memset(ne,0,sizeof(ne)) ;
  for(int i = 2 , j = 0 ; i <= n ; i ++){
    while(j && s[i] != s[j+1]) j = ne[j] ;
    if(s[i] == s[j+1]) j ++ ;
    ne[i] = j ; 
  }
  
}
int main(){
  int t = 0 ;
  while(cin >> n , n ){
    cin >> s+ 1;
    get_ne() ;
    printf("Test case #%d\n",++t) ;
    for(int i = 2 ; i <=n ;i ++){
      if(i %(i-ne[i]) == 0 && i /(i-ne[i]) > 1)
        printf("%d %d\n",i , i /(i-ne[i])) ;
    }
    cout << endl ;
  }
}