Make delicious recipes!

Pattern Matching (Rabin-Karp Algorithm)


Problem: Find all occurrences of pat[] of length ‘m’ in txt[] of length ‘n’

Solution: If we do a strcmp at every index of txt, then it would be O(mn)

Rabin-Karp algorithm for pattern matching matches pattern at every index of txt but adds one optimization.

It compares the hash-value of pattern with equal length substring at txt[i] before going for complete match.
This optimization reduces the chances of spurious matches quite a lot.

One more optimization added by Rabin-Karp Algorithm is that the hashing
function used in this algorithm should be able to calculate hash
incrementally
, so that when we move from txt[i] to txt[i+1], it should be
able to calculate the hash by just removing one character from the beginning
of earlier substring at txt[i] and adding character txt[i+1]

With these 2 optimizations, its is possible to have an average order of O(m+n)

Note: Worst case is still O(mn) when both the strings are like “aaaaa... aaa” and “aaaa” so
that the hash function always matches and we have to compare full strings at every index.



Like us on Facebook to remain in touch
with the latest in technology and tutorials!


Got a thought to share or found a
bug in the code?
We'd love to hear from you:

Name:
Email: (Your email is not shared with anybody)
Comment:

Facebook comments:

Site Owner: Sachin Goyal