powerstrings.java

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

package PKU.KMP;
import java.util.Scanner;


/**
 * ID:2406
 * KMP
 * @author yhm
 *
 */
public class PowerStrings {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		while(true){
			String str = cin.next();
			if(str.equals(".")) break;
			solve(str);
		}
	}
		
		static void solve(String str){
			if(str.length()==0) return;
			int[] next = computeNext(str);
			int size = str.length();
			int right = size-next[size];
			if(size%right==0){
				System.out.println(size/right);
			}
			else{
				System.out.println(1);
			}
		}
		
		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;
		}

}