String Matching Algorithms: KMP and Rabin-Karp For students.

String matching algorithms find where a pattern occurs inside a longer text — the engine behind Ctrl+F, search boxes, and DNA analysis. The two classics are KMP (Knuth-Morris-Pratt), which never re-checks characters it already matched, and Rabin-Karp, which compares numeric fingerprints (hashes) of text windows instead of the characters themselves.

They matter because the naive approach — checking the pattern at every position character by character — is too slow for big data. Searching a 3 GB genome or a billion-line server log needs an algorithm that skips ahead intelligently instead of restarting after every mismatch.

Key Concepts

• Pattern / Text: the string you seek (length m) and the string you search in (length n).
• Prefix function (KMP): π[i] = length of the longest proper prefix of pattern[0..i] that is also a suffix of it. This table tells KMP how far to slide after a mismatch without rescanning.
• Rolling hash (Rabin-Karp): a numeric fingerprint of a text window, updated in constant time as the window slides one step right.
• Spurious hit: the hash matches but the strings differ (a collision) — Rabin-Karp must verify with a direct character check.
• Alphabet size d: possible characters (256 for extended ASCII), used as the hash base.
• Modulus q: a prime the hash is taken modulo, keeping values small.

Formulas

• KMP time: O(n + m) — O(m) to build the prefix table, O(n) to scan the text once.
• Naive search: O(n × m) worst case, e.g. pattern "AAAAAB" in text "AAAAAAAAAA…".
• Rolling hash: h_next = (d × (h − T[i] × d^(m−1)) + T[i+m]) mod q, where h is the current window's hash. All values are integers modulo q.
• Rabin-Karp time: O(n + m) average; O(n × m) worst case if every window is a spurious hit (rare with a good prime).

Worked Example

Rabin-Karp: find P = "141" in T = "31415", with d = 10, q = 13.

1. Pattern hash: (1×100 + 4×10 + 1) mod 13 = 141 mod 13 = 11 (since 13×10 = 130).
2. First window "314": 314 mod 13 = 2 (13×24 = 312). 2 ≠ 11, no match.
3. Roll to "141": d^(m−1) mod q = 100 mod 13 = 9. Remove leading '3': 2 − 3×9 = −25 ≡ 1 (mod 13). Shift and add '1': (10×1 + 1) mod 13 = 11.
4. Hash 11 = pattern hash — hit at position 1. Verify characters: "141" equals "141" ✓.

Common Misconceptions

• "KMP is always faster than naive search." On short everyday texts the naive loop's tiny constant factors often win. KMP shines on long texts and repetitive patterns.
• "A hash match guarantees a match." It does not — collisions happen, so every hit needs a direct character comparison. Skipping verification is a classic bug.
• "Rabin-Karp is only for one pattern." Its real strength is multi-pattern search: hash each window once and look it up among the pattern hashes.

Real-World Applications

• Editors and IDEs: find/replace stays responsive on huge files.
• Plagiarism detection: fingerprints of document windows spot copied passages.
• Bioinformatics: searching billion-character DNA sequences for gene patterns.
• Spam filtering: multi-pattern matching scans messages for known phrases in one pass.

KMP wins by remembering what it already matched — its prefix table turns mismatches into smart jumps. Rabin-Karp wins by comparing cheap fingerprints and doing the expensive character check only on hits. Pick KMP for one pattern over a long text, Rabin-Karp for many patterns at once.