liveBook · Manning

Chapter 4: Rabin–Karp Algorithm

What you will learn in chapter 4 of Algorithms Every Programmer Should Know

Introduces Rabin–Karp as a hash-based way to search for a pattern in text, and explains how rolling hashes and collisions affect its performance.

After this chapter you will be able to

What it builds on

Section by section

Introduction

Introduces Rabin–Karp as a hash-based way to search for a pattern in text, and explains how rolling hashes and collisions affect its performance.

Key terms: Rabin–Karp algorithm, hash function, pattern, window, rolling hash, constant time, collision, O(n+m), O(nxm)

4.1 String matching algorithm

This section explains how Rabin–Karp searches for a string by hashing pattern-sized text windows, updating their hashes as the window slides, and checking actual characters when hashes match.

Key terms: hash function, pattern, window, hash, rolling hash, collision, spurious hits, character-by-character check, powers of 10, base-10 powers

4.2 Real world applications

The section introduces Rabin–Karp’s potential for large-scale systems and notes that deploying it in distributed production requires careful architectural engineering.

4.2.1 Plagiarism Detection

This section explains how plagiarism detection uses Rabin–Karp fingerprinting to find matching text, scales comparisons across large collections, and supplements exact matching with semantic techniques.

Key terms: plagiarism detection, Rabin-Karp, hashing, fingerprinting, full-text comparisons, data corpus, web crawlers, indexing, distributed storage, parallel processing

4.2.2 BioInformatics

This section explains how biological sequences can be searched as strings and why finding matches matters in bioinformatics.

Key terms: DNA, RNA, proteins, specialized alphabets, motif, whole-genome dataset, exact-match queries, Rabin-Karp algorithm, sequence similarity, homology

4.3 References

This section lists resources for further reading and practice on the Rabin–Karp algorithm and its applications.

4.4 Summary

Where this is used later

Concepts explained in this chapter

← Chapter 3: Hungarian Algorithm Chapter 5: Knuth-Morris-Pratt Algorithm →

These guides are generated from the text of Manning books by Manning's knowledge graph and link to the sections they draw on. The full books are available on liveBook and at manning.com.