lasvegas.java

这是根据算法设计课上讲的LasVegas算法用java实现的模式匹配算法

public class LasVegas
{
	public static String patternMatching(String X, String Y)
	{
		long primeNum=992;
		int j=1,n=X.length(),m=Y.length();
		long Wp=(long)(Math.pow((double)2,(double)m))%primeNum;
		//System.out.println("wp:"+Wp);
		long[] IpX=new long[n-m+2];
		long IpY=(Integer.parseInt(Y,2))%primeNum;
		//System.out.println("IpY:"+IpY);
	    String tempSubString=X.substring(0,m);
	    IpX[1]=Integer.parseInt(tempSubString,2);
	    while(j<(n-m+1))
	    {
	    	//System.out.println("loop:"+j);
	    	    if(IpX[j]==IpY) 
	    		   if(Y.equalsIgnoreCase(X.substring(j-1,j+m-1)))
	    		   return "Y is found at the position "+(j-1)+" of X";
	    
	    		long tempSum;
	    		//System.out.println("IpX["+j+"]: "+IpX[j]);
	    		tempSum=(2*IpX[j]-Wp*(Integer.parseInt(X.substring(j-1,j)))+Integer.parseInt(X.substring(j+m-1,j+m)))%primeNum;
	    		if(tempSum<0)
	    		{	    	
	    			IpX[j+1]=tempSum+primeNum;
	    			j++;
	    		}
	    		else if(tempSum<primeNum)
	    		{
	    			IpX[j+1]=tempSum;
	    			j++;
	    		}
	    		else
	    		{
	    			IpX[j+1]=tempSum-primeNum;	 
	    			j++;
	    		}
	    	
	    }
	    return "Y is not found in X!";
		
	}
	
	public static void main(String[] args)
	{
		String X="10111010111100001101011111001111011011100000011111001101011110100101111010101101101";
		String Y="100111101101110000011111001";	
		System.out.println(patternMatching(X,Y));
	}
}