Implemented Rabin-Karp algorithm in JAVA. Avoid using Math.pow().


  • 0
    H

    Rabin-Karp algorithm using a running hash. The Prime number for the hash function has to be tuned. If the prime number is small, we will get many hash collisions. If we use a large prime number, we might overflow the integer range. Also avoid using Math.pow() repeatedly as this is expensive.

        public int strStr(String haystack, String needle) {
        	primeMult = (int)Math.pow(PRIME, needle.length()-1);
        	
        	if(haystack.length()<needle.length()){
        		return -1;
        	}
        	int hashOfNeedle = getHash(needle);
        	int lenNeedle = needle.length();
        	int runnHash = getHash(haystack.substring(0, lenNeedle));
        	if(hashOfNeedle == runnHash && charByChar(haystack, needle, 0) == true)
        		return 0;
        	for(int i=lenNeedle ; i<=haystack.length()-1 ; i++){
        		runnHash = runningHash(runnHash, haystack.charAt(i-lenNeedle), haystack.charAt(i));
        		if(hashOfNeedle == runnHash && charByChar(haystack, needle, i-lenNeedle+1) == true)
        			return i-lenNeedle+1;
        	}
        	
        	return -1;
        }
        
        private boolean charByChar(String haystack , String needle , int pos){
        	for(int i=0 ; i<needle.length() ; i++ , pos++){
        		if( haystack.charAt(pos) != needle.charAt(i))
        			return false;
        		
        	}
        	return true;
        }
        
        private  final int PRIME = 7;
        
        private int primeMult = 0;
        
        private int runningHash(int hash, char o, char n ){
        	int oldVal = (int)o * primeMult ; 
        	hash =  ( hash - oldVal  ) * PRIME    +     (int)n * 1 ;
        	return hash;
        }
        
        private int getHash(String str){
        	int hash=0;
        	int pos = 1;
        	for(int i=str.length()-1 ; i>=0 ; i-- ){
        		
        		hash += (int)str.charAt(i) * pos;
        		pos *= PRIME;
        	}
        	return hash;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.