In RabinKarp Algorithm why compare hash first?

302 views Asked by At

In Rabin Karp substring search algorithm :

1) Calculate hash of the substring 2) Take a sliding window [equals the size of substring] and compare the hash of the string present in the window to that of substring. 3) If hash matches then we compare window content with the substring.

Question: 1) What is the benefit in terms of performance by matching hash first rather and then comparing ? Why we cannot just compare ? Comparing hash can be faster but how (i didn't get) ?

1

There are 1 answers

1
AudioBubble On BEST ANSWER

As the window slides, it only takes O(1) time to compute the new hash, and O(1) time to compare hashes.

Doing a full string comparison would take up to O(m) time every time you slide the window, where m is the length of the substring, and is likely to suffer from branch misprediction.