Implementing Rabin Karp String matching

2018-10-19 05:33:16

I am learning algorithms and have implemented the Rabin Karp algorithm. Can anyone please determine if the implementation is correct or not? I didn't implemented rolling HashCode. Coes it still count as correct?

This algorithm got accepted here, but it's 7ms than the str.indexOf() implementation of 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();