String Matching Algorithms

What you'll learn

• The Problem

  Given a text T of length n and a pattern P of length m, find all occurrences of P in T. Naive approach: For each position in T, check if P matches starting there → O(n × m). Goal: Achieve O(n + m) or close to it by avoiding redundant com…

• KMP (Knuth-Morris-Pratt)

• Key Insight

  When a mismatch occurs after matching some characters, we already know what some of the next characters are (they're part of the pattern we just matched). The prefix function (partial match table) tells us the longest proper prefix of th…

• Prefix Function (Failure Function)

  For a pattern P, lps[i] = length of the longest proper prefix of P[0..i] which is also a suffix of P[0..i].

• Building the Prefix Function — O(m)

  Why this is O(m): length can increase at most m times total (bounded by i advancing). Each time we fall back (length = lps[length-1]), length decreases. Total decreases ≤ total increases ≤ m, so total iterations ≤ 2m.

• KMP Search — O(n)

• Trace

  ---

• Rabin-Karp (Rolling Hash)

• Key Insight

  Instead of comparing characters, compare hash values of the pattern and each text window. If hashes match, verify with actual character comparison (to handle collisions). The rolling hash updates in O(1) when the window slides.

• Rolling Hash Function

  Use polynomial hashing with a base (e.g., 26 for lowercase letters) and a modulus (large prime): When sliding window right (remove leftmost char, add new rightmost char):

• Implementation

• When to Use Rabin-Karp Over KMP

  | Scenario | Better Choice | |----------|--------------| | Single pattern search | KMP (guaranteed O(n+m)) | | Multiple pattern search simultaneously | Rabin-Karp (compute hash for each pattern) | | 2D pattern matching | Rabin-Karp (roll…

• Z-Algorithm (Bonus: Another O(n+m) Approach)

• Concept

  For string S, Z[i] = length of the longest substring starting at i that matches a prefix of S. Trick: Concatenate pattern + separator + text as "P$T". Any Z[i] == m means pattern found at that position in text. ---

• Comparison

  | Algorithm | Preprocessing | Search | Space | Best For | |-----------|--------------|--------|-------|----------| | Naive | None | O(nm) | O(1) | Short patterns, quick implementation | | KMP | O(m) | O(n) | O(m) | Single pattern, guaran…

• Applications Beyond Simple Matching

  | Application | Technique | |-------------|-----------| | Find all anagrams of pattern in text | Sliding window with frequency map (O(n)) | | Longest repeated substring | Binary search on length + rolling hash | | Shortest palindrome (ad…

• Problem Recognition

  | Signal | Algorithm | |--------|-----------| | "Find pattern in text" | KMP or Rabin-Karp | | "Multiple patterns simultaneously" | Rabin-Karp or Aho-Corasick | | "Longest prefix which is also suffix" | KMP prefix function directly | | "…