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:

• @course@Rabin Karps Algorithm
• @course@Optimization: Precomputation
• @course@Optimization: Implementation and Analysis
• @video@Lecture 9: Table Doubling, Karp-Rabin
• @video@Rolling Hashes, Amortized Analysis
• @feed@Explore top posts about Data Science