lasvegas.java

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

public class LasVegas {
	
	private String T;
	private String P;
	private int f[];
	private int p;
	
	LasVegas(String T,String P,int p){
		this.T = T;
		this.P = P;
		int l = P.length();
		f = new int[l];
		this.p = p;
	}
    
	int pMatching(){
		int m = P.length();
		int n = T.length();
		int Ipx = Integer.parseInt(T.substring(0,m),2)%p;
		int Ipy = Integer.parseInt(P,2)%p;
		//System.out.println(Ipy);
		int Wp = ((int) Math.pow(2,m))%p;
		int j = 0;
		for(;j < n-m;){
			if(Ipx==Ipy)
				{
				int i=0;
				for(;i<m;i++){
					if(T.charAt(j+i)!=P.charAt(i))
						break;
				}
				if(i!=m){
					Ipx = (2*Ipx-Wp*(T.charAt(j)-48)+T.charAt(j+m)-48)%p;
					if(Ipx<0)
						Ipx=Ipx+p;
					j++;
					continue;
				}
				else return j;
				}
			else{
				Ipx = (2*Ipx-Wp*(T.charAt(j)-48)+T.charAt(j+m)-48)%p;
				if(Ipx<0)
					Ipx=Ipx+p;
				//System.out.println(Ipx);
				j++;
			}
		}
		if(Ipx==Ipy)
		{
			int i=0;
			for(;i<m;i++){
				if(T.charAt(j+i)!=P.charAt(i))
					break;
			}
			if(i==m) return j;
			}
		return -1;
	}
	
	public static void main(String[] args) {
		String T = "11011110001010110110110011100111";
		String P = "111011000";
		LasVegas m = new LasVegas(T,P,17);
		System.out.print(m.pMatching());
		
	}
}