Poj Solution 1961

http://poj.org/problem?id=1961

//* @author:
import java.util.Scanner;   
  
public class Main {   
    static int next[]=new int[1000010];

    public static void main(String[] args) {   
        Scanner scn = new Scanner(System.in); 
        int n;        
        String input = "";   
        int j=0;
        int k=0;
        while(scn.hasNext()){  
            n=scn.nextInt(); 
            input = scn.next(); 
             if(n==0){  
                break;
             } 
           getNext(input,n);
           System.out.printf("Test case #%dn",++k);
           

           /* �������� */ 
          for (int i = 2; i <= n; i++){ 
            /* ������β�ظ��Ӵ��ij��� */
            j = i - next[i];
            /* �������ظ��������ظ��Ӵ���Ϊ���� */
             if (i % j == 0 && i / j > 1){
                System.out.printf("%d %dn", i, i / j); 
              }
           }
           System.out.printf("n");
        }   
       
      
    }   

   public static void getNext(String T,int len) {//��bģʽ��T��next[]��
    int i = 0;
    int j = next[0] = -1;
    
    while (i< len)
     if (0 > j || T.charAt(i) == T.charAt(j)) {//ƥ��
        j++; i++;
        next[i] = j;
     }else//ʧ��
       j = next[j];
  }
}