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

• 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;
}
``````

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