liveBook · Manning

String match

As explained in Algorithms Every Programmer Should Know

String matching is the computational task of locating exact or approximate occurrences of one character sequence within another.

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

How Algorithms Every Programmer Should Know covers it

How deep it goes
Works from direct character comparisons through rolling hashes and collision checks, but does not detail semantic matching internals.
Examples
Compares COOL against ALICEANDJOEBAKEDCOOKIES and applies fingerprinting to plagiarism checks across document collections.
What you can do after
Apply Rabin–Karp to find pattern positions by hashing text windows and verifying character matches.
How it connects
Connects pattern search with hashing, rolling hash, plagiarism detection, semantic matching, and natural language processing.

Also explained in

Compare how 2 books explain string match →

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Algorithms Every Programmer Should Know. The section links point to the parts of the book it draws on.