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[i1] * BASE;
// 'needle' hash
int hash = 0;
for (int i=0; i<len; i++) hash += N[i]*base[len1i];
// 'haystack' start hash
int h = 0;
for (int i=0; i<len; i++) h += H[i] * base[len1i];
if (h == hash) return 0;
// Search
for (int i=len; i < H.length; i++) {
h = BASE * (h  (H[ilen] * base[len1])) + H[i];
if (h == hash) {
// strickt compare
for (int j=0; j<len; j++) {
if (H[ij] != N[len1j]) continue;
}
return ilen+1;
}
}
return 1;
}
Accepted Java code. Simple Rabin–Karp implementation.


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[ij] != N[len1j]) continue, I think it should be if (H[ij] != N[len1j]) break;you should add the condition to return the value "if (j == len) return ilen+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; }

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.