I am learning algorithms and have implemented the Rabin-Karp string search algorithm. I didn't implement a rolling HashCode
, but it's judged correct by this online judge.
It's slower than the str.indexOf()
implementation (7ms, compared to 4 ms). Can this be improved? What is the time complexity for this?
class Solution {
public int strStr(String haystack, String needle) {
if (haystack == null || needle == null)
return -1;
int needleHash = hashCode(needle);
int plen = needle.length();
boolean t = true;
int tlen = haystack.length() - needle.length() + 1;
for (int i = 0; i < tlen; i++) {
String sub = haystack.substring(i, plen + i);
int haystackHash = hashCode(sub);
if (haystackHash == needleHash) {
for (int j = 0; j < plen; j++) {
char[] charN = needle.toCharArray();
char[] charH = sub.toCharArray();
if (charN[j] != charH[j]) {
t = false;
}
}
if (t == true) {
return i;
}
}
}
return -1;
}
public int hashCode(String value) {
int h = 777;
if (value.length() > 0) {
char val[] = value.toCharArray();
for (int i = 0; i < val.length; i++) {
h = 31 * h + val[i];
}
}
return h;
}
}