period.java

来自「PKU中一些数据结构基本算法题的java实现」· Java 代码 · 共 61 行

package PKU.KMP;

import java.util.Scanner;


/**
 * ID:1961
 * KMP
 * @author yhm
 *
 */
public class Period {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		int i=0;
		while(true){
			int size = cin.nextInt();
			if(size==0) break;			
			i++;
			String str = cin.next();
			System.out.println("Test case #"+i);
			solve(str);
		}
	}
		
		static void solve(String str){
			if(str.length()==0) return;
			int[] next = computeNext(str);
			int size = str.length();
			for(int i=2;i<=size;i++){
				int right = i-next[i];
				if(i%right==0){
					if(i/right==1) continue;
					System.out.print(i);
					System.out.println(" "+i/right);
				}
			}
			System.out.println();
		}
		
		static int[] computeNext(String str){
			int size = str.length();
			int[] next= new int[size+1];
			next[0] = -1;
			next[1] = 0;
			for(int i=2;i<=size;i++){
				int j = next[i-1]+1;
				while(j>0&&(str.charAt(i-1)!=str.charAt(j-1))){
					j=next[j-1]+1;
				}
				next[i]=j;
			}
			return next;
		}

}