Rabin-Karp Algorithm for string matching
This algorithm is based on the concept of hashing.
This algorithm was authored by Rabin and Karp in 1987.
Problem: Given two strings — a pattern ss and a text tt, determine if the pattern appears in the text and if it does, enumerate all its occurrences in O(|s|+|t|)O(|s|+|t|) time.
Algorithm: Calculate the hash for the pattern ss. Calculate hash values for all the prefixes of the text tt. Now, we can compare a substring of length |s||s| with ss in constant time using the calculated hashes. So, compare each substring of length |s||s| with the pattern. This will take a total of O(|t|)O(|t|) time. Hence the final complexity of the algorithm is O(|t|+|s|)O(|t|+|s|): O(|s|)O(|s|) is required for calculating the hash of the pattern and O(|t|)O(|t|) for comparing each substring of length |s||s| with the pattern.
