String Algorithm Visualizations
Substring search looks simple until a mismatch arrives. The naive response is to slide the pattern one place and start over. String algorithms earn their speed by saving work: a reusable border, a rolling fingerprint, or an index built for many future queries.
KMP saves a structural fact about the pattern: a suffix already matched may also be a prefix, so the text cursor does not need to move backward. Rabin-Karp saves a numeric fingerprint of the current window, then updates it as the window moves. A suffix array spends more up front, sorting every suffix start once so later substring queries can use binary search.
Three ways to avoid restarting
| Algorithm | Saved state | Preprocessing | One query |
|---|---|---|---|
| KMP | prefix-suffix lengths in the LPS table | O(m) | O(n + m) |
| Rabin-Karp | pattern and window fingerprints | O(m) | O(n + m) expected, O(nm) worst case |
| Suffix Array | suffix start indices in lexicographic order | O(n log^2 n) in this lesson | O(m log n) |
KMP does pattern-specific preprocessing and gives a deterministic linear bound. Rabin-Karp's scan is compact and makes window reuse explicit, but an equal fingerprint still needs an exact character check. A suffix array is the heavier index: it pays when one text will receive many queries.
A recommended order
Start with KMP String Matching. Its LPS table makes the central invariant visible: after a mismatch, the algorithm can retain a prefix that is also a suffix of what already matched. Watch the text cursor stay pinned while the pattern falls back. The included broken variant advances the text cursor at that moment and misses a real occurrence.
Then open Rabin-Karp. Here the pattern does not stretch or fall back; a fixed-width window moves one position at a time. Watch the outgoing digit leave the rolling formula, the incoming digit enter, and the fingerprint update without rereading the middle of the window. The default input also supplies the important warning: 31428 and 31415 share a hash modulo 13, yet character verification rejects the first one.
Finish with Suffix Array. Its default BANANA run shows why repeated prefixes are awkward and how prefix doubling turns them into pairs of integer ranks. Once the suffix starts settle into lexicographic order, the same canvas switches to lower-bound binary search for ANA.
What to watch in the animations
- In KMP, distinguish the retained length from the distance the pattern moves. They are related, but they are not the same quantity.
- In Rabin-Karp, notice when the pattern row is absent. A different hash lets the algorithm skip every character comparison for that window.
- In Suffix Array, watch the
-1end sentinel. It is what putsAbeforeANAwhen the visible prefix is otherwise tied. - Follow each failure case. The useful idea is clearest when one tempting line changes or one favorable assumption breaks.
All string algorithm visualizations
Choose a lesson below, change its input, and step through the trace alongside the highlighted Python or JavaScript code.