--- # === IDENTITY === id: software/patterns/string-matching-kmp-rabin-karp/2026 canonical_question: "How do string matching algorithms work (KMP, Rabin-Karp)?" aliases: - "KMP algorithm explained" - "Rabin-Karp string search" - "string pattern matching algorithms comparison" - "failure function prefix table KMP" - "rolling hash string matching" - "Z-algorithm string search" - "Boyer-Moore vs KMP vs Rabin-Karp" entity_type: software_reference domain: software > patterns > string matching algorithms region: global jurisdiction: global temporal_scope: 1977-2026 # === VERIFICATION === last_verified: 2026-02-24 confidence: 0.95 version: 1.0 first_published: 2026-02-24 # === TEMPORAL VALIDITY === temporal_validity: status: stable last_breaking_change: null next_review: 2026-08-23 change_sensitivity: low # === CONSTRAINTS === constraints: - "KMP failure function array must be 0-indexed with lps[0] = 0; 1-indexed implementations cause off-by-one errors" - "Rabin-Karp hash modulus must be a large prime (e.g., 10^9+7); small moduli cause excessive spurious hits" - "Rolling hash arithmetic must use modular arithmetic consistently to avoid integer overflow" - "Rabin-Karp worst case is O(nm) when all hash values collide; always verify hash matches with full comparison" - "Multi-pattern search requires Aho-Corasick or Rabin-Karp with multiple hashes; KMP handles only single patterns" # === SKIP CONDITIONS === skip_this_unit_if: - condition: "Looking for fuzzy/approximate string matching (edit distance, Levenshtein)" use_instead: "Edit distance / Levenshtein algorithms" - condition: "Need regex pattern matching with wildcards and groups" use_instead: "Regular expression engines (NFA/DFA-based)" - condition: "Searching for substring in a single string in production code" use_instead: "Use built-in str.find() / String.indexOf() / strings.Contains() — they already use optimized algorithms" # === AGENT HINTS === inputs_needed: - key: pattern_type question: "Are you searching for a single pattern or multiple patterns simultaneously?" type: choice options: ["single_pattern", "multiple_patterns"] - key: text_size question: "How large is the text you are searching through?" type: choice options: ["small", "large", "streaming"] - key: guarantee_needed question: "Do you need guaranteed worst-case performance or is average-case sufficient?" type: choice options: ["guaranteed_worst_case", "average_case_ok"] # === DISTRIBUTION === canonical_source: "https://knowledgelib.io/software/patterns/string-matching-kmp-rabin-karp/2026" suggested_citation: "Source: knowledgelib.io — AI Knowledge Library (verified 2026-02-24)" # === RELATED UNITS === related_kos: depends_on: [] related_to: - id: "software/patterns/trie-prefix-tree/2026" label: "Trie & Prefix Tree Patterns" - id: "software/patterns/bloom-filters/2026" label: "Bloom Filters" - id: "software/patterns/binary-search-variations/2026" label: "Binary Search Variations" solves: [] alternative_to: [] often_confused_with: - id: "software/patterns/regex-engine-internals/2026" label: "Regex Engine Internals (NFA/DFA)" # === SOURCES (7 authoritative sources) === sources: - id: src1 title: "Knuth-Morris-Pratt algorithm" author: Wikipedia url: https://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm type: community_resource published: 2025-12-15 reliability: high - id: src2 title: "Rabin-Karp algorithm" author: Wikipedia url: https://en.wikipedia.org/wiki/Rabin%E2%80%93Karp_algorithm type: community_resource published: 2025-11-20 reliability: high - id: src3 title: "Rabin-Karp Algorithm for string matching" author: CP-Algorithms url: https://cp-algorithms.com/string/rabin-karp.html type: technical_blog published: 2025-06-10 reliability: high - id: src4 title: "KMP Algorithm for Pattern Searching" author: GeeksforGeeks url: https://www.geeksforgeeks.org/dsa/kmp-algorithm-for-pattern-searching/ type: community_resource published: 2025-09-14 reliability: moderate_high - id: src5 title: "String-matching algorithms: Rabin-Karp, KMP and Aho-Corasick" author: Pavel Safronov url: https://medium.com/tech-in-depth/string-matching-algorithms-271d50a2a265 type: technical_blog published: 2024-03-15 reliability: moderate_high - id: src6 title: "String Matching Algorithms — University of Auckland CS369" author: University of Auckland url: https://www.cs.auckland.ac.nz/courses/compsci369s1c/lectures/GG-notes/CS369-StringAlgs.pdf type: academic_paper published: 2024-01-01 reliability: high - id: src7 title: "Introduction to String Searching Algorithms" author: TopCoder url: https://www.topcoder.com/community/competitive-programming/tutorials/introduction-to-string-searching-algorithms/ type: community_resource published: 2023-08-01 reliability: moderate_high --- # String Matching Algorithms: KMP, Rabin-Karp & Beyond ## TL;DR - **Bottom line**: Use KMP for guaranteed O(n+m) single-pattern matching; use Rabin-Karp for multi-pattern search or when hashing is natural; use your language's built-in `find()`/`indexOf()` for production single-pattern search. - **Key tool/command**: Failure function (KMP) / rolling hash (Rabin-Karp) — the preprocessing step that makes each algorithm efficient. - **Watch out for**: Hash collisions in Rabin-Karp degrade worst case to O(nm); always verify hash matches with full character comparison. - **Works with**: Any language; algorithms are language-agnostic. Standard in competitive programming, text editors, bioinformatics, and plagiarism detection. ## Constraints - KMP failure function array must be 0-indexed with `lps[0] = 0`; 1-indexed implementations cause off-by-one errors - Rabin-Karp hash modulus must be a large prime (e.g., 10^9+7); small moduli cause excessive spurious hits - Rolling hash arithmetic must use modular arithmetic consistently to avoid integer overflow in languages without arbitrary precision integers (Java, C++, JavaScript) - Rabin-Karp worst case is O(nm) when all hash values collide; always verify hash matches with full string comparison [src2] - Multi-pattern search requires Aho-Corasick or Rabin-Karp with multiple hashes; KMP handles only single patterns [src5] ## Quick Reference | Algorithm | Preprocessing | Search Time | Space | Multi-pattern | Best For | |---|---|---|---|---|---| | Naive (brute force) | None | O(nm) | O(1) | No | Short patterns, small texts | | KMP | O(m) | O(n) | O(m) | No | Single pattern, guaranteed linear time | | Rabin-Karp | O(m) | O(n) avg, O(nm) worst | O(1) | Yes | Multi-pattern, plagiarism detection | | Boyer-Moore | O(m + sigma) | O(n/m) best, O(nm) worst | O(m + sigma) | No | Long patterns, large alphabets | | Aho-Corasick | O(sum of m_i) | O(n + matches) | O(sum of m_i * sigma) | Yes | Dictionary matching, many patterns | | Z-Algorithm | O(n+m) | O(n+m) | O(n+m) | No | Simpler alternative to KMP | Where: n = text length, m = pattern length, sigma = alphabet size. [src1] [src6] ## Decision Tree ``` START ├── Single pattern or multiple patterns? │ ├── MULTIPLE PATTERNS ↓ │ │ ├── Fixed dictionary of patterns? │ │ │ ├── YES → Aho-Corasick (O(n + total_matches)) │ │ │ └── NO (patterns change) → Rabin-Karp with multiple hashes │ │ └── END │ └── SINGLE PATTERN ↓ ├── Need guaranteed worst-case O(n+m)? │ ├── YES → KMP or Z-Algorithm │ └── NO (average case OK) ↓ ├── Pattern length > 10 and large alphabet (ASCII/Unicode)? │ ├── YES → Boyer-Moore (sublinear average case) │ └── NO ↓ ├── Production code (not competitive programming)? │ ├── YES → Use built-in: str.find() / indexOf() / strings.Contains() │ └── NO ↓ └── DEFAULT → KMP (most versatile, easiest to implement correctly) ``` ## Step-by-Step Guide ### 1. Build the KMP failure function (LPS array) The Longest Proper Prefix which is also Suffix (LPS) array is the core of KMP. For each position `i` in the pattern, `lps[i]` stores the length of the longest proper prefix of `pattern[0..i]` that is also a suffix. This tells KMP how far to shift after a mismatch without re-examining characters. [src1] ```python def build_lps(pattern): m = len(pattern) lps = [0] * m length = 0 # length of previous longest prefix suffix i = 1 while i < m: if pattern[i] == pattern[length]: length += 1 lps[i] = length i += 1 else: if length != 0: length = lps[length - 1] # don't increment i else: lps[i] = 0 i += 1 return lps ``` **Verify**: `build_lps("ABABAC")` -> expected output: `[0, 0, 1, 2, 3, 0]` ### 2. Run KMP search using the LPS array With the LPS array built, scan the text. On a mismatch at position j in the pattern, jump to `lps[j-1]` instead of restarting from 0. Each text character is examined at most twice, guaranteeing O(n+m) total. [src1] [src4] ```python def kmp_search(text, pattern): n, m = len(text), len(pattern) lps = build_lps(pattern) matches = [] i = j = 0 # i = text index, j = pattern index while i < n: if text[i] == pattern[j]: i += 1 j += 1 if j == m: matches.append(i - j) j = lps[j - 1] elif i < n and text[i] != pattern[j]: if j != 0: j = lps[j - 1] else: i += 1 return matches ``` **Verify**: `kmp_search("ABABDABABCABABABABCABAB", "ABABC")` -> expected output: `[5]` ### 3. Implement Rabin-Karp rolling hash Choose a base (e.g., 256 for ASCII) and a large prime modulus. Compute the hash of the pattern and the first window. For each subsequent position, update the hash in O(1) by removing the leading character and adding the trailing character. [src2] [src3] ```python def rabin_karp(text, pattern, base=256, mod=10**9 + 7): n, m = len(text), len(pattern) if m > n: return [] # Precompute: base^(m-1) % mod h = pow(base, m - 1, mod) # Compute initial hashes p_hash = t_hash = 0 for i in range(m): p_hash = (p_hash * base + ord(pattern[i])) % mod t_hash = (t_hash * base + ord(text[i])) % mod matches = [] for i in range(n - m + 1): if p_hash == t_hash: # Verify character by character (avoid false positives) if text[i:i + m] == pattern: matches.append(i) if i < n - m: # Roll the hash: remove leading char, add trailing char t_hash = (t_hash - ord(text[i]) * h) % mod t_hash = (t_hash * base + ord(text[i + m])) % mod return matches ``` **Verify**: `rabin_karp("ABABDABABCABABABABCABAB", "ABABC")` -> expected output: `[5]` ### 4. Implement Z-Algorithm as a simpler KMP alternative The Z-array for a string S stores at each position i the length of the longest substring starting at i that matches a prefix of S. Concatenate `pattern + "$" + text` and compute the Z-array; any position with `z[i] == m` is a match. [src6] ```python def z_function(s): n = len(s) z = [0] * n z[0] = n l = r = 0 for i in range(1, n): if i < r: z[i] = min(r - i, z[i - l]) while i + z[i] < n and s[z[i]] == s[i + z[i]]: z[i] += 1 if i + z[i] > r: l, r = i, i + z[i] return z def z_search(text, pattern): concat = pattern + "$" + text z = z_function(concat) m = len(pattern) return [i - m - 1 for i in range(m + 1, len(concat)) if z[i] == m] ``` **Verify**: `z_search("ABABDABABCABABABABCABAB", "ABABC")` -> expected output: `[5]` ## Code Examples ### Python: KMP with all match positions > Full script: [python-kmp-with-all-match-positions.py](scripts/python-kmp-with-all-match-positions.py) (25 lines) ```python # Input: text string and pattern string # Output: list of all starting indices where pattern occurs in text def kmp_find_all(text, pattern): """KMP string matching - O(n+m) guaranteed.""" n, m = len(text), len(pattern) # ... (see full script) ``` ### JavaScript: Rabin-Karp with BigInt for safe modular arithmetic > Full script: [javascript-rabin-karp-with-bigint-for-safe-modular.js](scripts/javascript-rabin-karp-with-bigint-for-safe-modular.js) (26 lines) ```javascript // Input: text (string), pattern (string) // Output: array of starting indices of all matches function rabinKarp(text, pattern) { const n = text.length, m = pattern.length; if (m > n) return []; # ... (see full script) ``` ### Java: KMP implementation > Full script: [java-kmp-implementation.java](scripts/java-kmp-implementation.java) (29 lines) ```java // Input: text (String), pattern (String) // Output: List of all starting indices import java.util.ArrayList; import java.util.List; public static List kmpSearch(String text, String pattern) { # ... (see full script) ``` ## Anti-Patterns ### Wrong: Restarting pattern comparison from scratch on mismatch ```python # BAD -- O(nm) naive approach re-examines characters unnecessarily def naive_search(text, pattern): matches = [] for i in range(len(text) - len(pattern) + 1): if text[i:i+len(pattern)] == pattern: # creates new string each time matches.append(i) return matches ``` ### Correct: Use KMP to avoid redundant comparisons ```python # GOOD -- O(n+m) with failure function, no backtracking in text def kmp_search(text, pattern): lps = build_lps(pattern) i = j = 0 matches = [] while i < len(text): if text[i] == pattern[j]: i += 1; j += 1 if j == len(pattern): matches.append(i - j) j = lps[j - 1] elif i < len(text) and text[i] != pattern[j]: j = lps[j - 1] if j else 0 if j == 0 and text[i] != pattern[0]: i += 1 return matches ``` ### Wrong: Rabin-Karp without verifying hash matches ```python # BAD -- trusts hash equality without character comparison (false positives!) if p_hash == t_hash: matches.append(i) # WRONG: hash collision = wrong match ``` ### Correct: Always verify hash matches with full comparison ```python # GOOD -- hash is a filter, not proof; always confirm if p_hash == t_hash: if text[i:i+m] == pattern: # O(m) verification only on hash match matches.append(i) ``` ### Wrong: Using small modulus in Rabin-Karp ```python # BAD -- mod=101 causes frequent collisions on any real text mod = 101 t_hash = (t_hash * base + ord(text[i])) % mod ``` ### Correct: Use a large prime modulus ```python # GOOD -- 10^9+7 is a standard large prime that fits in 64-bit integers mod = 10**9 + 7 t_hash = (t_hash * base + ord(text[i])) % mod ``` ## Common Pitfalls - **Hash collisions degrade Rabin-Karp to O(nm)**: When many substrings produce the same hash, every position triggers a full comparison. Fix: use double hashing (two independent hash functions with different primes) to reduce collision probability to ~1/n^2. [src2] - **1-indexed vs 0-indexed LPS array**: Many textbook descriptions use 1-indexed arrays; translating to 0-indexed code without adjusting causes off-by-one bugs. Fix: always initialize `lps[0] = 0` and start the build loop at `i = 1`. [src1] - **Integer overflow in rolling hash**: In Java/C++/JavaScript (without BigInt), `base^(m-1)` overflows 64-bit integers for long patterns. Fix: apply `% mod` at every multiplication step, or use language-specific big integer types. [src3] - **Negative modular arithmetic**: In languages where `%` can return negative values (C++, Java, JavaScript), the rolling hash subtraction step can produce negative hashes. Fix: add `mod` before taking `%`: `t_hash = ((t_hash - c * h) % mod + mod) % mod`. [src3] - **Forgetting to handle empty pattern**: Both KMP and Rabin-Karp can infinite-loop or return wrong results on empty pattern input. Fix: check `if len(pattern) == 0: return []` at the start. [src4] - **Using KMP for multi-pattern search**: KMP preprocesses one pattern at a time; running it k times for k patterns gives O(k*(n+m)), which is worse than Aho-Corasick's O(n + total_pattern_length + matches). Fix: use Aho-Corasick for multi-pattern. [src5] ## When to Use / When Not to Use | Use When | Don't Use When | Use Instead | |---|---|---| | Need guaranteed O(n+m) worst case for single pattern | Production code where stdlib is available | `str.find()`, `indexOf()`, `strings.Contains()` — already optimized | | Searching multiple patterns simultaneously | Pattern includes wildcards or regex features | Regex engine or NFA/DFA-based matcher | | Streaming text (can't backtrack, e.g., network packets) | Text fits in memory and pattern is short (<5 chars) | Naive search or stdlib (overhead not worth it) | | Competitive programming / interview questions | Need approximate/fuzzy matching | Edit distance, BK-trees, or fuzzy matching libraries | | Text editor find/replace with very long documents | Searching in sorted data | Binary search | | Plagiarism detection across many documents | Need only first occurrence in small text | `str.find()` / `indexOf()` | ## Important Caveats - Standard library string search functions (Python `str.find()`, Java `String.indexOf()`, Go `strings.Contains()`) typically use optimized variants of Boyer-Moore or two-way algorithm and are faster than hand-rolled KMP for most practical inputs. Implement KMP/Rabin-Karp only when you need specific properties (streaming, multi-pattern, or guaranteed worst case). - Rabin-Karp's practical speed depends heavily on the hash function quality. The polynomial rolling hash with a large prime mod is standard, but for adversarial inputs (competitive programming with hacking), use double hashing or randomize the base. - Boyer-Moore often outperforms KMP in practice for large alphabets (ASCII/Unicode) because it achieves sublinear average-case O(n/m) by skipping characters. However, its worst case is O(nm) without the Galil rule optimization. - The Z-algorithm produces identical results to KMP with a simpler implementation; prefer it when code clarity matters more than constant-factor performance. ## Related Units - [Trie & Prefix Tree Patterns](/software/patterns/trie-prefix-tree/2026) - [Bloom Filters](/software/patterns/bloom-filters/2026) - [Binary Search Variations](/software/patterns/binary-search-variations/2026)