kmp.java

数据结构中字符串匹配的三种经典算法－－KMP算法、MonteCarlo算法、LasVegas算法。分别实现将两个0/1串的匹配。并作为比较。Java语言编写。

public class KMP {
	private String T;
	private String P;
	private int f[];
	
	KMP(String T,String P){
		this.T = T;
		this.P = P;
		int l = P.length();
		f = new int[l];
	}
	
	void fail(){  //对模式P计算失效函数
		int lengthP = P.length();
		f[0] = -1;
		for(int j = 1;j<lengthP;j++){
			int i = f[j-1];
			while((P.charAt(j) != P.charAt(i+1))&&i >= 0)i = f[i];
			if(P.charAt(j) == P.charAt(i+1))f[j] = i+1;
			else f[j] = -1;			
		}		
	}
	int pMatching(){
		int posT = 0,posP = 0;
		int lengthT = T.length();
		int lengthP = P.length();
		fail();
		while(posP < lengthP&&posT < lengthT)
			if(P.charAt(posP) == T.charAt(posT)){  //对应字符匹配
				posP++;
				posT++;
			}
			else if(posP == 0) posT++;
			     else posP = f[posP-1]+1;
		 if(posP < lengthP) return -1;  // 匹配失败
		 else return posT - lengthP;    // 匹配成功
	}

	public static void main(String[] args) {
		String T = "101100010111111010110000110";
		String P = "110000110";
		//String T = "11011110001010110110110011100111";
		//String P = "111011000";
		
		KMP k = new KMP(T,P);
		System.out.print(k.pMatching());
		
	}
}