seekthenameseekthefame.java

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

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


/**
 * ID:2752
 * KMP
 * 
 * @author yhm
 *
 */
public class SeektheNameSeektheFame {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		while(cin.hasNextLine()){
			String str = cin.nextLine();
			solve(str);
		}


	}

	static void solve(String str){
		if(str.length()==0) return;
		List<Integer> l = new ArrayList<Integer>();
		l.add(str.length());
		int[] next = computeNext(str);
		int i=str.length();
		while(true){
			if(next[i]==0){
				break;
			}
			l.add(next[i]);
			i=next[i];
		}
		int num = l.size()-1;
		while(num>0){
			System.out.print(l.get(num)+" ");
			num--;
		}
		System.out.println(l.get(0));
	}
	
	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;
	}
}