public class RabinKarp {
private long needleHash;
private int M;
private long Q;
private int R = 256;
private long RM;
public long hash(String key, int M) {
//compute hash for key[0..M-1]
long h = 0;
for(int j = 0; j < M; j ++) {
h = (R*h + key.charAt(j)) % Q;
}
return h;
}
public RabinKarp(String needle) {
this.M = needle.length();
Q = 997; //A long random prime, larger the value (10 power 20), less chance the result is incorrect.
RM = 1;
for(int i = 1; i <= M-1; i++) {
RM = (R * RM) % Q;
}
needleHash = hash(needle, M);
}
private int search(String haystack) {
int N = haystack.length();
long txtHash = hash(haystack, M);
if(needleHash == txtHash) return 0; //Match at beginning
for(int i = M; i < N; i++) {
txtHash = (txtHash + Q - RM*haystack.charAt(i-M) % Q) % Q;
txtHash = (txtHash*R + haystack.charAt(i)) % Q;
if(needleHash == txtHash) return i - M + 1; //we don't check because check need store backup string of haystack
}
return -1;
}
public static void main(String...args) {
String haystack = "search a needle in a haystack.";
RabinKarp rk = new RabinKarp("needle");
System.out.println(rk.search(haystack));
}
}
