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) ?
As the window slides, it only takes
O(1)
time to compute the new hash, andO(1)
time to compare hashes.Doing a full string comparison would take up to
O(m)
time every time you slide the window, wherem
is the length of the substring, and is likely to suffer from branch misprediction.