LearnViz CompSci
Home / Learn / Algorithms / Rabin-Karp Algorithm

Advanced Topic 44 of 51 Algorithms

Rabin-Karp Algorithm

String search using rolling hashes.

How it works

Rabin-Karp searches for a pattern by comparing hash values of the pattern and each window of the text. A rolling hash updates the hash of the next window in O(1) by removing the leading character and adding the next, so the average time is O(n + m). When hashes match, the characters are compared to rule out collisions.

Step-by-step walkthrough

  1. Compute a hash of the pattern.
  2. Hash the first text window of the same length.
  3. Sliding by one character updates the hash in O(1) by removing the old letter and adding the new one.
  4. If hashes differ, the window cannot match.
  5. If hashes match compare the characters to rule out a collision.

Where it is used

Plagiarism detection, searching for many patterns of the same length at once, finding duplicate chunks in files, two-dimensional pattern matching and content-defined chunking in backups use Rabin-Karp.

Common pitfall

A weak or small modulus gives many false matches and can degrade to O(nm). Forgetting to verify the match after a hash hit yields wrong results. Negative values after subtracting need modular adjustment. Choose a large prime modulus and a good base, and consider double hashing against adversarial inputs.

Where it fits in the course

Rabin-Karp Algorithm is topic 44 of 51 in Algorithms, rated Advanced. It follows KMP Algorithm. The next topic is Huffman Coding.

Practice and explore

How to study this topic

  1. Read the explanation above and restate the definition in your own words.
  2. Open the interactive lesson and answer its mini quiz.
  3. Read the common pitfall, then write a short example that avoids it.
  4. Check your understanding in the Algorithms quiz, and revisit the topic if you miss a question.

Frequently asked questions

What is Rabin-Karp Algorithm?
String search using rolling hashes. It belongs to Algorithms and is an advanced-level topic.
Where do people use Rabin-Karp Algorithm?
Plagiarism detection, searching for many patterns of the same length at once, finding duplicate chunks in files, two-dimensional pattern matching and content-defined chunking in backups use Rabin-Karp.
What is the most common mistake with Rabin-Karp Algorithm?
A weak or small modulus gives many false matches and can degrade to O(nm).
What should I learn before this topic?
Start with KMP Algorithm, the topic just before it in Algorithms.
How can I practice it?
Answer the mini quiz in the interactive lesson, then take the Algorithms quiz.
Is Rabin-Karp Algorithm hard to learn?
It is an Advanced topic. Expect to read the explanation more than once and to connect it with earlier topics. Working through a small example by hand helps most.
How long does it take to learn Rabin-Karp Algorithm?
Most learners can read the explanation and finish the interactive lesson in under an hour. Fluency comes from applying the idea, so plan a few short practice sessions with the quiz.
Which topics are related to Rabin-Karp Algorithm?
KMP Algorithm, Huffman Coding, Maximum Flow are closely connected. The full list is in the related topics section of this page.
What should I study after Rabin-Karp Algorithm?
Continue with Huffman Coding, the next topic in Algorithms.

Related topics