kmp.java

PKU中一些数据结构基本算法题的java实现

package OTHERS;

import java.util.Scanner;

public class KMP {
	static int[] computeNext(String str){
		int size = str.length();
		int[] next= new int[size];
		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;
	}
	
	static int SringMatch(String A,String B){
		int start = -1;
		int sizeOfA = A.length();
		int sizeOfB = B.length();
		int[] next = computeNext(B);
		int i=0,j=0;
		while(start==-1&&i<sizeOfA){
			if(B.charAt(j)==A.charAt(i)){
				j++;
				i++;
			}
			else{
				j = next[j];
				if(j==-1){
					j=0;
					i++;
				}
			}
			if(j==sizeOfB){
				start = i-sizeOfB;
			}
		}
		return start;
	}
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
        String A = "xyxxyxyxyxx";
        String B = "xyxy";
        System.out.println(SringMatch(A,B));

	}
}