String matching locates a pattern inside a text. A direct approach slides the pattern along the text and compares characters; Rabin–Karp instead compares hashes for equal-length windows, checking the characters when hashes match. section 4.1
Rabin–Karp searches a text by repeating these steps:
- Map characters to numbers and compute hashes for the pattern and the first text window. section 4.1
- Slide the window one character at a time, updating its hash by removing the outgoing character and adding the incoming one. section 4.1
- When hashes match, compare the actual characters to rule out collisions; record verified matches. section 4.1
Figure 4.1 The pattern COOL is to be matched with the text “ALICEANDJOEBAKEDCOOKIES”. Each character is checked one by one. The first box shows that A and C are compared. With no successful match, we move the pattern forward by one character and continue comparing. The second box shows three characters matched, and the last character doesn’t, concluding the pattern is not in the text only after checking the first three characters.
Follow the direct comparison of COOL against ALICEANDJOEBAKEDCOOKIES: three characters match at one position before the final character reveals a mismatch. section 4.1
Plagiarism screening
A plagiarism detector can use Rabin–Karp fingerprints to filter document segments before full-text comparison. Large-scale systems may distribute comparisons across servers; detecting paraphrases or conceptual similarity also involves semantic matching and NLP. section 4.2.1

