Published by Dimitris Kougioumtzis · Updated
Precompute pattern borders to skip redundant comparisons after a mismatch.
On mismatch, use the pattern's prefix table to keep the useful part of the match without rescanning text.
When to use Knuth–Morris–Pratt string search
Deterministic linear-time single-pattern matching.
Choosing an alternative
Rabin-Karp relies on hash filtering and exact verification.
Worked example: input and state changes
Example input
ABABABCABAB | ABABC
These checkpoints follow the actual example timeline. State details show the stored values and decisions; use the visualization to inspect every intervening step.
Step 0: Initial state.
State at this checkpoint
{ "values": [ "A", "B", "A", "B", "A", "B", "C", "A", "B", "A", "B" ], "active": [] }Step 5: Compare text index 0 with pattern index 0.
State at this checkpoint
{ "values": [ "A", "B", "A", "B", "A", "B", "C", "A", "B", "A", "B" ], "active": [ 0 ], "pattern": "ABABC", "lps": [ 0, 0, 1, 2, 0 ], "matches": [] }Step 10: Fall back to pattern border length 2.
State at this checkpoint
{ "values": [ "A", "B", "A", "B", "A", "B", "C", "A", "B", "A", "B" ], "active": [ 4 ], "pattern": "ABABC", "lps": [ 0, 0, 1, 2, 0 ], "matches": [] }Step 14: Match at index 2.
State at this checkpoint
{ "values": [ "A", "B", "A", "B", "A", "B", "C", "A", "B", "A", "B" ], "active": [], "pattern": "ABABC", "lps": [ 0, 0, 1, 2, 0 ], "matches": [ 2 ] }Step 19: Matches at indices: 2.
State at this checkpoint
{ "values": [ "A", "B", "A", "B", "A", "B", "C", "A", "B", "A", "B" ], "active": [], "pattern": "ABABC", "lps": [ 0, 0, 1, 2, 0 ], "matches": [ 2 ] }
Expected final state
Matches at indices: 2.
Complexity and input bounds
Family: Strings. Time complexity: O(n + m).
Space complexity: O(m) prefix table, excluding matches.
Working-space bounds describe algorithm state and any explicitly noted output, excluding the visualization's saved timeline. Recording frames can use more memory than running the function alone. Here n is sequence length, V and E are vertex and edge counts, and other parameters refer to the named input dimensions.
Text | pattern. Use 1–40 letters for text and 1–16 for pattern.
The playground validates these limits before starting. Downloaded functions are callable implementations, with parameter and output-buffer contracts in their comments; they do not all repeat the playground's input validation.
Common mistakes and limitations
After a full match, fall back through prefix links so overlapping matches remain discoverable.
Further reading
For background on algorithm analysis and the JavaScript function interface:
- MIT OpenCourseWare: algorithm design and analysis foundations
- MDN: JavaScript function parameters and return values
Editorial and testing approach · Browse all algorithm guides
Complete JavaScript implementation
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | // Character-code arrays, n ≤ 40 and 1 ≤ m ≤ 16. Writes all overlapping match indices and returns their count. Reference snippets assume validated playground inputs. Fixed scratch buffers have 256 slots. Sorting variants may use a different traversal strategy than the animation. function algorithm(text, n, pattern, m, matches) { if (m == 0) { return 0; } let lps = Array(256).fill(0); let i = 1; let j = 0; while (i < m) { if (pattern[i] == pattern[j]) { j++; lps[i++] = j; } else if (j > 0) { j = lps[j - 1]; } else { i++; } } i = 0; j = 0; let count = 0; while (i < n) { if (text[i] == pattern[j]) { i++; j++; if (j == m) { matches[count++] = i - j; j = lps[j - 1]; } } else if (j > 0) { j = lps[j - 1]; } else { i++; } } return count; } |
Source
Primary research source for the algorithm or its underlying method. The playground is a bounded teaching implementation, not the publication's original program.
- Fast Pattern Matching in Strings
Donald E. Knuth; James H. Morris, Jr.; Vaughan R. Pratt (1977). Research paper.