Rabin-Karp’s algorithm

Rabin-Karp algorithm is a string searching algorithm that uses hashing to find any one of a set of pattern strings in a text. For strings of average length n, it performs in O(n+m) time with O(m) space, where m is the length of the pattern. It is often used in bioinformatics to search for DNA patterns.

Visit the following resources to learn more:

• Rabin Karps Algorithm
• Optimization: Precomputation
• Optimization: Implementation and Analysis
• Lecture 9: Table Doubling, Karp-Rabin
• Rolling Hashes, Amortized Analysis