# Accepted Java code. Simple Rabin–Karp implementation.

• ``````private static final int BASE = 31;

public int strStr(String haystack, String needle) {
char[] H = haystack.toCharArray();
char[] N = needle.toCharArray();
int len = N.length;

// Edge cases
if (len == 0) return 0;
if (H.length < len) return -1;

// Base
int[] base = new int[len];
base[0] = 1;
for (int i=1; i<len; i++) base[i] = base[i-1] * BASE;

// 'needle' hash
int hash = 0;
for (int i=0; i<len; i++) hash += N[i]*base[len-1-i];

// 'haystack' start hash
int h = 0;
for (int i=0; i<len; i++) h += H[i] * base[len-1-i];
if (h == hash) return 0;

// Search
for (int i=len; i < H.length; i++) {
h = BASE * (h - (H[i-len] * base[len-1])) + H[i];
if (h == hash) {
// strickt compare
for (int j=0; j<len; j++) {
if (H[i-j] != N[len-1-j]) continue;
}
return i-len+1;
}
}

return -1;
}``````

• This post is deleted!

• Your code is very elegant and clean.
Although your code is passed OJ, I think there are some problems in your code. In the double loop, your code: if (H[i-j] != N[len-1-j]) continue, I think it should be if (H[i-j] != N[len-1-j]) break;

you should add the condition to return the value "if (j == len) return i-len+1;".

"if (h == hash) return 0;" also should be changed to "if (h == hash && haystack.substring(0, len). equals(needle)) return 0;"

• I used Java's String.hashCode() method to implement Rabin Karp, here's my solution:

``````    public int strStr(String str, String substr) {
int i, n = str.length(), m = substr.length();;
int hashPattern = substr.hashCode();
for (i = 0; i < n - m + 1; i ++ ) {
int hs = str.substring(i, i + m).hashCode();
if (hs == hashPattern) return i;
}
return -1;
}``````

• That's really not Rabin-Karp. You missed its entire point. And actually made it less efficient than a naive search. And it doesn't even work, for example you fail the input "baaaaacbaacbb", "abcacaaaabaac".

• You're right as it doesn't use rolling hash so it recomputes the hash of the substring at each iteration. The reason your test case doesn't work is because I used Java's native hashCode() function, it was sufficient for leetcode's test cases. Normally you would want to implement a much better hash function.

• No, the reason it fails is that you're doing it wrong. If the current substring's hash matches, then you ought to also check the current substring itself.

• What is the Base=31 for?

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