Rabin-Karp Algorithm

Last updated Nov 8, 2022 Edit Source

1. Convert the pattern (length m) to a number p
2. Convert the first m-characters (the first text window) to a number t with a hash function
3. If p and t are equal, there is possibility of pattern: verify against the actual pattern
4. Rolling hash function: shift the text window one character to the right and convert the new string
5. Repeat until pattern is found or exit

The new hash value can be calculated in $\theta(m)$ time.

Rabin-Karp can support wildcard matches by simply considering the position of the wildcard to be a value of 0: