Knuth–Morris–Pratt search: the idea
Prerequisites: String matching, prefixes, suffixes, and array indices.
A prefix begins at the start of a string; a suffix ends at its end. KMP first builds a prefix table for the pattern. Each entry records the length of the longest proper prefix that is also a suffix of the pattern through that position. Proper means shorter than the whole substring. On a mismatch, this table tells the search how much of its already matched prefix can be kept. The text cursor never moves backward.
Try it
Choose Repeated prefix and step through both table construction and text search. Watch j fall back through the prefix table while i stays put. Choose Overlapping: after a complete match, fallback preserves a suffix that could begin another match.
Reading the display
During preprocessing, pink pattern cells are compared and the prefix table grows. During search, i is the text cursor and j is the matched-prefix length. A mismatch can change the alignment without consuming the current text character.
Time and memory
O(n + m) time and O(m) working space excluding returned matches. Counters separate prefix-building tests from text-search tests.
The bounds above describe core work on prepared input. String conversion to code-point arrays and editor validation are additional work. The visualization saves the data at each operation so you can step backward. This recording requires extra time and memory beyond the algorithm’s own working storage. Input limits keep the demonstrations manageable.
When to use it—and what to watch
Pays a preprocessing cost to avoid repeated text work. Exact, case-sensitive matching only. This teaching version splits strings into Unicode code points; it does not normalize accents or combine grapheme clusters.
Continue exploring
- Naïve string matching — Try the pattern at every possible starting position.