Why does KMP run in O(n+m) when a naive scan can degrade to O(n*m)?
answer
- Watch the text pointer, not the pattern
- Naive wastes work by re-comparing
- Count how often the matched length rises
- It can only fall as often as it rose
- At most about 2n comparisons total
basics
~20 sKMP never moves its text pointer backward. On a mismatch it shrinks the matched pattern length using the precomputed table instead of restarting the text one position later, so the scan costs O(n) after an O(m) table build.
solid answer
~50 sThe naive scan restarts: after failing deep inside a window it slides one position right and re-compares characters it has already read, which is why a pattern like many `a`s ending in `b` against a long run of `a`s costs about n*m comparisons. KMP keeps two indices — the text position `i` and the matched length `j` — and `i` never decreases. On a mismatch it sets `j = fail[j-1]`, keeping the longest still-valid matched prefix rather than throwing the work away. Counting is easy: `j` grows by one only when `i` advances, so it grows at most n times over the whole scan; each fallback strictly decreases `j`, and `j` never drops below zero, so there can be at most n fallbacks in total. That bounds comparisons at roughly 2n, plus O(m) to build the table.
code
pseudocode · 14 lines// p = pattern (length m), t = text (length n), fail = prefix table
i = 0 // text position
j = 0 // number of pattern chars matched so far
while i < length(t)
if t[i] == p[j]
i = i + 1
j = j + 1
if j == m
report match starting at i - m
j = fail[j - 1]
else if j > 0
j = fail[j - 1] // note: i does NOT change here
else
i = i + 1go deeper
Recall the headline: the text pointer never rewinds, so the scan is linear after a linear-size setup, while the naive version can re-read the same characters over and over.
Be able to trace the loop and give the counting argument out loud: the matched length rises at most once per text step and can only fall as often as it rose, bounding total comparisons.
Show you can name the input shape that actually triggers naive's worst case and judge whether your real data ever resembles it, rather than quoting worst-case labels as if they were measurements.
Own the framing that a hard worst-case ceiling is a reliability property, not a speed property, and be able to say when your system is buying predictability rather than throughput.
## Where the naive scan melts down The naive algorithm picks a starting offset in the text, compares forward until a mismatch, then bumps the offset by one and starts the comparison over. On ordinary text this is fine — most windows die on the first or second character. The meltdown is a specific shape: a pattern that is almost entirely one repeated character with a distinguishing character at the end, run against a text made of that same repeated character. Say the signature is a run of `a`s finished by `b`, and the stream is a long run of `a`s. Every window matches nearly the whole pattern and fails on the final character, then the scan slides one byte right and re-compares nearly the whole window again. The work is about n*m comparisons, and almost every one of them re-examines a character the scan had already looked at. That re-examination is the entire waste, and it is what KMP removes. ## The two indices KMP maintains `i`, a position in the text, and `j`, the number of pattern characters currently matched ending at `i-1`. The invariant is: `text[i-j .. i-1] == pattern[0 .. j-1]`. Both a match and a plain-mismatch-at-zero advance `i`; nothing ever decreases it. On a mismatch with `j > 0`, the algorithm does not touch `i` at all — it only shrinks `j` to `fail[j-1]`, the longest prefix of the pattern that is still consistent with the text characters already read. The invariant survives the shrink, because that border is by definition also a suffix of the region just matched. ## The counting argument The bound falls out of watching `j`: - `j` increases by exactly one on each successful comparison, and every successful comparison also advances `i`. Since `i` runs from 0 to n and never goes back, `j` increases at most n times over the entire scan. - Every fallback strictly decreases `j`, since `fail[j-1] < j` always (the border is a *proper* prefix). - `j` starts at 0 and never goes negative. A quantity that starts at zero, goes up at most n times, and only ever comes down in strict steps cannot come down more than n times. So the total number of fallbacks over the whole scan is at most n, and the total number of character comparisons is at most about 2n. Add the O(m) table build and you have O(n + m) worst case — a hard bound, not an expected one, with no assumption about the input distribution and no randomness anywhere. ## The direction of the claim matters Three precise statements that candidates routinely blur: 1. **The text pointer never moves backward — that is not the same as "each text character is compared once."** While `j` falls through a chain of borders, `i` stays put and the same text character may be compared against several successively shorter pattern prefixes. What is bounded is the *total*, not the per-character count. 2. **KMP is never sublinear.** It looks at essentially every character of the text. Skip-based families such as Boyer-Moore-Horspool can jump over characters entirely and beat KMP handily on typical text with a longish pattern — but their worst cases degrade, whereas KMP's does not. "Linear" here is a ceiling worth having, not a speed record. 3. **O(n*m) is naive's worst case, not its behaviour.** On varied text the naive inner loop almost never runs deep, so its expected work is close to n. An interviewer who hears "naive is quadratic" flatly will push back. ## Reading the loop The attached fragment is the whole scan. Three things to point at when tracing it: the `else if j > 0` branch is the only interesting one, and note what it does *not* contain — any change to `i`; a full match reports and then falls back via the same table entry, which is how overlapping occurrences come out for free; and the final `else` (mismatch with nothing matched) is the only place a text character is consumed without any pattern progress. Trace it on the meltdown case and the contrast is vivid: after failing on the final character, `j` drops by one, the very next text character matches, and the scan walks the run of repeated characters at one comparison per position instead of re-reading the entire window. ## Accounting for the two terms The `m` is the table build and is paid once per pattern. The `n` is the scan. Space is O(m) for the table plus a couple of indices — no copy of the text, no buffer of what has been read, nothing that grows with n. That combination of a strict linear ceiling and pattern-sized state is what people are buying when they choose KMP, and it is the honest way to state the guarantee.
- Does KMP ever compare the same text character more than once?Yes. When the matched length falls through a chain of borders, the text index stays put and that same character is compared against shorter and shorter pattern prefixes. The guarantee is on the total — roughly 2n comparisons — not on a per-character count of one.
- Where does the +m in O(n+m) come from, and when do you stop paying it?It is the prefix-table build, which is a self-match of the pattern against its own tail. You pay it once per pattern, so searching many texts for the same fixed signature amortizes it away entirely; searching one short text for a fresh long pattern is where it actually shows up in the bill.
- Can KMP be sublinear the way skip-based matchers are?No. It advances through the text one position at a time and effectively inspects every character, so n is a floor as well as a ceiling. Skip-based algorithms can leap over stretches of text and often win on typical inputs, at the cost of worst cases KMP does not have.
saying these in an interview costs you the question
- Says KMP compares each text character exactly once
- Claims KMP skips ahead in the text
- States naive matching is quadratic on all inputs
- Says the table makes the search sublinear
- Cannot say which index never moves backward