Naïve string matching: the idea
Prerequisites: Strings, character positions, and comparing characters.
A string is a sequence of characters. A pattern is the smaller string we want to locate inside a text. The naïve algorithm aligns the pattern with each possible text position and compares characters from left to right. A mismatch moves the alignment one position forward. A full match records that starting index. This version finds all occurrences, including overlapping matches.
Try it
Choose Repeated prefix. Many candidate alignments agree for a while before failing. Switch to KMP with the same text and pattern and compare character tests. Choose Overlapping to find starts 0, 1, and 2.
Reading the display
The pattern is positioned beneath the text. Pink marks the current comparison; cyan marks characters already matched in the current alignment. The match list stores zero-based starting indices.
Time and memory
O(nm) worst-case character comparisons, O(1) working space excluding returned matches. n is text length and m is pattern length.
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
Simple and effective for short patterns. Rechecking a long repeated prefix can be costly. Empty patterns are excluded here to avoid ambiguity about which positions count as matches.
Continue exploring
- Knuth–Morris–Pratt search — Reuse matched prefixes instead of restarting after a mismatch.