String matching (or pattern searching) finds all occurrences of a pattern string within a text string. The naive approach slides the pattern one position at a time and compares character by character — simple but potentially slow at O(n·m) in the worst case.
This visualisation shows the naive algorithm, which is the foundation every developer should understand before learning optimised variants like KMP or Boyer-Moore. Seeing exactly where the O(n·m) cost comes from — at every mismatch, the pattern shifts only one step — makes the motivation for smarter algorithms immediately clear.
Align the pattern at each text position from 0 to n-m. Compare character by character. On a full match, record the position. On any mismatch, shift the pattern one step right and start over.
For each of the n-m+1 starting positions, up to m comparisons are needed. Worst case: text 'AAAAAB' and pattern 'AAAB' — every alignment compares all m characters before failing at the last one.
Unlike some search algorithms, naive string matching continues after finding a match and reports every occurrence. This correctly handles overlapping patterns like finding 'ABA' in 'ABABA'.
KMP improves this to O(n+m) Knuth-Morris-Pratt precomputes a failure function that tells the algorithm how far to jump after a mismatch — skipping redundant comparisons. O(n+m) total, never revisiting a character.
TIPWatch the mismatch steps closely. Every time the pattern mismatches, it shifts only one position right — even if several characters already matched. KMP fixes exactly this: it skips positions guaranteed not to match based on the pattern's internal structure.