3.8.1 · D5String Algorithms
Question bank — Naive pattern matching — O(nm)
Reminders before you start (so no symbol is unearned):
- = the big text, length (the long sentence).
- = the small pattern, length (the little word on the transparent ruler).
- A shift = the position in where we lay the left edge of the ruler.
- A valid shift = a place where all letters of line up with .
- Early break = stop spelling the moment one letter mismatches.
True or false — justify
Each answer starts with the verdict, then the reason — the reason is the point.
The naive algorithm can miss a match if the pattern appears twice in a row.
False — it tests every shift independently, so overlapping or repeated occurrences are all found (e.g. "ABA" in "ABABA" at and ).
Naive matching is always regardless of input.
False — that is only the worst case. On typical text mismatches hit within the first 1–2 characters, so the inner loop rarely nears and it behaves like .
If there is exactly one candidate shift.
True — the count is , namely ; the ruler fills the whole text and can only sit in one place.
Removing the early break changes which matches are reported.
False — the break is a speed optimization only; with or without it the same shifts are reported, you just pay more comparisons without it.
If the first characters , we still must compare the rest of that shift.
False — a single mismatch kills the shift, so we break immediately and slide to ; comparing further would be wasted work.
Naive matching needs the text to fit in memory but never modifies it.
True — it only reads and , comparing characters; it writes nothing back, so both stay unchanged.
The worst case requires a pattern that never actually occurs in the text.
False in general — the worst case is about doing maximum work per shift, not about absence of matches; "AAA" in "AAAAA" does full work and matches at several shifts.
A longer pattern always makes naive matching slower.
False — a longer raises the per-shift cost but shrinks the number of shifts (); a rare long pattern can mismatch early and finish faster than a short common one.
Naive matching and KMP return exactly the same set of valid shifts.
True — both solve the same substring search problem and are correct; they differ only in speed, never in the answer.
If is empty (), the algorithm reports a match at every position.
True — the count and the inner loop runs zero comparisons (
j==m holds instantly), so every shift is trivially valid.Spot the error
Find why the reasoning breaks, in one or two sentences.
"Loop from to so we cover the whole text." — what's wrong?
For the ruler runs off the end of , causing out-of-bounds access on ; the correct upper bound is inclusive.
"I already matched 'ABA' at , so I can skip those characters at ." — what's wrong?
Naive matching deliberately forgets all prior comparisons and restarts at each shift; reusing that info is exactly the leap that turns naive into KMP, not naive itself.
"To speed it up, I'll compare all chars first, then check a flag." — what's wrong?
Without the early break you always perform comparisons even after an obvious first-letter mismatch, throwing away the free speedup; break on the first mismatch instead.
"Naive is basically the sliding window, so it must be ." — what's wrong?
The window slides by one, but at each stop we may re-spell up to characters from scratch, so total work is , not the of a window that reuses computation.
"The number of comparisons is ." — what's wrong?
The outer loop runs times (positions through inclusive), so the bound is ; dropping the undercounts by one full shift.
"If a mismatch happens at , the shift wasted 2 comparisons; the first one at was pointless." — what's wrong?
Nothing is wasted — comparisons at had to succeed to reach ; they are exactly the work that confirmed a partial match before the break fired.
"Naive matching's cost depends only on ." — what's wrong?
It depends on both and (and the input pattern); the same with a longer or self-similar can multiply the per-shift work up to .
Why questions
Force the reason to the surface.
Why does the outer loop stop at and not later?
Beyond there are fewer than characters of left, so the pattern cannot physically fit — any match there is impossible.
Why is "AAAA…A" with pattern "AAA…AB" the killer input?
Every shift matches the leading A's and only fails on the last character, so the early break never fires early and each shift pays the full comparisons → .
Why can naive matching be on English text but on a DNA-like "AAAA" string?
English has a large alphabet, so mismatches appear within 1–2 characters; a tiny repetitive alphabet lets partial matches run deep before failing, maximizing inner-loop length.
Why is the algorithm "correct by exhaustion"?
A match can only start at one of the candidate positions, and naive matching explicitly tests every one of them, so it cannot skip a valid shift.
Why does dropping constants turn into ?
In Big-O we keep the dominant growth term; since , the product is bounded above by a constant times , and lower-order pieces vanish for large inputs.
Why doesn't naive matching benefit from knowing the pattern's internal structure?
It treats each shift as a blank restart and never inspects against itself; algorithms like KMP and Boyer–Moore precompute that structure to skip ahead, which is precisely what naive gives up.
Why is reporting all shifts (not just the first) harder to short-circuit?
Even after finding one match we must keep sliding to the end, because later positions may also be valid; we cannot stop early without risking missed occurrences.
Edge cases
The scenarios the reader must never be surprised by.
(pattern longer than text): how many shifts?
Zero — , so the outer loop never runs and no match is possible; the pattern simply can't fit.
(single-character pattern): what does the algorithm reduce to?
A plain linear scan — each shift does at most one comparison, giving shifts and total, the best possible case for naive.
(identical strings): what is reported?
Exactly one match at , found after the full comparisons succeed; the single candidate shift is valid.
Empty text () with non-empty pattern: result?
No shifts and no matches — , so the loop body never executes.
Both empty (): result?
One match at — the empty pattern matches the empty text at the single position, since and the inner loop passes with zero comparisons.
Pattern occurring at overlapping positions, e.g. "AA" in "AAA": which shifts are valid?
Both and — naive tests each shift independently, so overlaps are reported without any special handling.
Text where the pattern never appears: how much work still happens?
Anywhere from (early mismatches) up to (deep partial matches); absence of a match does not guarantee cheap work.
Recall One-line summary of every trap
Naive matching is correct by exhaustion and fast on random text but in the worst case, checks shifts, restarts from scratch each time, and reports every valid shift — including overlaps and empty-string edge cases.
Connections
- Naive pattern matching — O(nm) — the parent this bank drills.
- KMP Algorithm — the upgrade that reuses matched info instead of restarting.
- Boyer-Moore Algorithm — skips ahead using character rules.
- Rabin-Karp Algorithm — replaces char comparison with hashing.
- Big-O Notation — the language of the bound.
- Sliding Window Technique — the "slide the ruler" mental model.
- Substring Search Problem — the problem all of these solve.