Stating the problem precisely
Before any clever method, pin down exactly what we are asked to do. We are given a long string called the text T of length n, and a short string called the pattern P of length m, with m at most n. The exact string matching problem asks: at which positions does P appear inside T as a contiguous block? A match at position i means the m characters T[i], T[i+1], ..., T[i+m-1] equal P[0], P[1], ..., P[m-1] exactly, character by character. We usually want every such i, not just the first.
Two things in that definition matter a lot. First, matching must be contiguous and aligned: P has to sit as one unbroken window over T, so "ana" matches inside "banana" twice (at positions 1 and 3) even though those two windows overlap. Second, the characters come from some alphabet — the set of allowed symbols, like the 26 letters, the 4 DNA bases, or all 256 byte values. The size of that alphabet quietly shapes how hard or easy the problem is, as we will see when comparisons start to behave very differently on tiny versus huge alphabets.
The naive method and why it feels right
The most natural idea is also the first one anyone invents. Slide the pattern along the text one position at a time, and at each alignment check whether the window matches, character by character, until a mismatch or a full match. This is naive matching, a textbook instance of the brute-force paradigm: there are n - m + 1 possible starting positions, so just try them all and verify each. It is obviously correct because it literally tests the definition at every position — nothing clever, nothing to doubt.
for i = 0 .. n-m: # each starting position
j = 0
while j < m and T[i+j] == P[j]:
j = j + 1 # extend the match
if j == m: report match at iOn everyday text this is often perfectly fast. Searching for "cat" in an English paragraph, most alignments die on the very first character — the text letter is not 'c', so the inner loop quits after a single comparison and we slide on. When mismatches come early and cheaply, the total work is close to n comparisons, which is why naive matching survives in real editors for short searches. Its good behaviour, though, is an average-case story that leans on the text and pattern not sharing long stretches of structure.
Where the naive method bleeds
The trouble shows up when matches almost succeed again and again. Take the text "aaaaaaaaab" (nine a's then a b) and the pattern "aaaab". At the first alignment we happily match four a's, then the b in the pattern hits an a in the text — mismatch on the fifth comparison. We slide one position right and do the exact same thing: four a's, then fail. Every alignment costs nearly m comparisons before failing, and there are about n alignments, so the total climbs to roughly n times m comparisons.
That worst case is Theta(n*m), and with m as large as n/2 it is Theta(n^2) — quadratic in the text length. The deep reason is wasteful forgetting. When the pattern matched "aaaa" and then failed, we already learned something true about the text: those four characters were all a's. But the naive method throws that knowledge away, slides over by just one, and rediscovers most of it from scratch. It re-reads text characters it has already seen, sometimes m times each. The information was there; we simply did not keep it.
The one insight behind every fast method
The pattern is known to us in advance, and that is the lever. Before we even look at the text, we can study P by itself and discover its internal repetitions — places where a prefix of the pattern equals a suffix of a piece of it. Those self-overlaps tell us, the instant a mismatch happens at a given alignment, how much of the partial match is still guaranteed to line up after we shift. We can then slide the pattern forward by more than one, sometimes by a lot, without any risk of skipping a real match.
- Preprocess the pattern alone to summarize its self-overlaps — this is where Knuth-Morris-Pratt builds its prefix function and the Z-algorithm builds its Z-array.
- Scan the text once, never moving the text pointer backwards; on a mismatch, use the precomputed summary to shift the pattern by as much as is safe.
- Because each text character is examined a bounded number of times, the search phase costs O(n), and the whole method costs O(n + m).
That O(n + m) is the prize: linear time, the n for scanning the text plus the m for studying the pattern, with no quadratic blow-up no matter how repetitive the input is. It is worth pausing on why this is the right yardstick — you must at least read the text and the pattern once to be sure of the answer, so O(n + m) is essentially the best any exact matcher can hope for. The fast algorithms in this rung are different routes to that same linear floor.
A map of this rung
Different algorithms turn the one insight into machinery in different ways, and the rest of this rung walks through them. Knuth-Morris-Pratt summarizes the pattern with a prefix function that records, for each position, the longest proper prefix that is also a suffix, and uses it to never re-read a text character. The Z-algorithm computes, for the string itself, how far each position agrees with the start, giving a clean linear matcher and a tool you will reuse far beyond matching. Both reach O(n + m) by deterministic, comparison-based reasoning.
Two other ideas take entirely different angles. Rolling hashes in Rabin-Karp turn each window into a number that can be updated in constant time as the window slides, trading exactness for speed: it is a randomized method whose expected time is O(n + m), but a careless hash can suffer collisions, so it is fast on average rather than guaranteed in the worst case. Meanwhile Aho-Corasick generalizes KMP to search for many patterns at once, and suffix arrays and suffix trees preprocess the text instead of the pattern, so that after one heavier build you can answer many queries quickly.
Keep one honest caveat in mind as you climb. The linear bound is a worst-case asymptotic promise, and asymptotics hides constants; for a short pattern in ordinary text, the simple naive scan can beat KMP because its inner loop is so cheap, the hidden-constant pitfall in action. The point of this rung is not that fancy always wins, but that you should understand exactly what each method buys you and what it costs — so you can choose the right tool when the repetitive, adversarial, or many-pattern cases arrive.