Pattern searching - Rabin Karp - based on hash value

RabinKarp.java

/******************************************************
 * RABIN KARP FINGERPRINT SUBSTRING SEARCH
 * 
 * Performs hash operation to check for match 
 * Uses horner's method to compute hash value
 * 
 * A total N-M substring hash values are computed 
 * and matched with the hash function of pattern
 * 
 * Time - O(N)
 * 
 * MonteCarlo version -          is linear          -correct[with high probability]
 * Las Vegas version  -linear[with high probability]-correct   
 * 
 ******************************************************/

public class RabinKarp {
	
	private String pat;
	private int M,R=256;
	private long RM,patHash,Q; // computing R^(M-1)%Q
	
	public RabinKarp(String pat){
		this.pat =pat; this.M = pat.length();
		this.Q = 997; //long random prime
		RM=1;
		for(int i=0; i<M; i++){
			RM = (R*RM)%Q;
		}
		
		patHash = hash(pat,M);
		
	}
	
	private long hash(String key, int M){
		long h=0; 
		for(int i=0;i<M; i++){
			h = (R*h + key.charAt(i)) %Q;
		}
		return h;
	}
	
	public boolean check(int i){
		return true;
	}
	
	public int search(String txt){
		int N = txt.length();
		long txtHash = hash(txt,M);
		if(patHash==txtHash) return 0;
		for(int i=M; i<N-M; i++){ //Remove leading digit, add trailing digit and check for match
			txtHash = (txtHash + Q - RM*txt.charAt(i-M)%Q) %Q;
			txtHash = (txtHash*R + txt.charAt(i))%Q;
			if(patHash==txtHash){
				if(check(i-M+1)) return i-M+1;
			}
		}
		return N;
	}
	
}