montecarlo.java

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

public class MonteCarlo {
	
	private String T;
	private String P;
	private int f[];
	private int p;
	
	MonteCarlo(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;
		//System.out.println(Wp);
		int j=0;
		for(;j < n-m;){
			if(Ipx==Ipy)
				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)
			return j;
		return -1;
	}
	
	public static void main(String[] args) {
		String T = "101100010111111010110000110";
		String P = "110000110";
		MonteCarlo m = new MonteCarlo(T,P,17);
		System.out.print(m.pMatching());
		
	}
}