KMP algorithm — failure function, O(n+m) — full derivation: Question bank

The pseudocode we keep referring to

So that "the standard KMP pseudocode" is never a mystery, here it is in full — first the build of $π$ , then the scan of $T$ .

# --- build the failure function of the pattern P (length m) ---
pi[0] = 0
j = 0
for i = 1 .. m-1:
    while j > 0 and P[i] != P[j]:
        j = pi[j-1]          # fall back down the nested-border chain
    if P[i] == P[j]:
        j += 1
    pi[i] = j
 
# --- scan the text T (length n) using pi ---
j = 0
for i = 0 .. n-1:
    while j > 0 and T[i] != P[j]:
        j = pi[j-1]          # mismatch: slide pattern, DO NOT move i back
    if T[i] == P[j]:
        j += 1
    if j == m:               # full match ending at text index i
        report match at i - m + 1
        j = pi[m-1]          # keep overlap so we catch overlapping matches

Every question below refers to exactly these two loops.

Before we start, one word we lean on everywhere: a border of a string is a proper prefix that is also a suffix. That is exactly what $π [i]$ measures — the length of the longest border of $S [0.. i]$ . (See Borders and Periods of Strings for the deeper theory of borders.)

True or false — justify

Each item is Statement ::: Verdict + one-line reason.

π [0] = 0

for every possible string.

True. A single character

S [0]

has no proper prefix (a proper prefix must be strictly shorter), so its longest border has length

0

The failure function depends only on the pattern

P

, never on the text

T

True.

π

is built from

P

alone; the text is only consumed later in the match loop, which is why we can precompute

π

once and reuse it.

π [i]

can be larger than

i

False. A border of

S [0.. i]

is a proper prefix, so its length is at most

i

(the substring has

i + 1

characters);

π [i] \leq i

always.

π [i] = k > 0

, then it is guaranteed that

S [k]

(the char right after the border) may or may not equal

S [i]

— the border says nothing about the next char.

True. The border only certifies that

S [0.. k - 1] = S [i - k + 1.. i]

; the character following the border in the prefix is unconstrained.

For a string of all identical characters like aaaa, we have

π = [0, 1, 2, 3]

True. Each prefix's longest border is the whole string minus one char (a,aa,aaa), giving values

0, 1, 2, 3

Two different patterns can never share the same failure-function array.

False. abab and cdcd both give

π = [0, 0, 1, 2]

;

π

captures the pattern of repetition, not the actual letters.

In the match loop the text pointer

i

can decrease when a mismatch pushes

j

back via

π [j - 1]

False. Only

j

falls back;

i

is inside a for that marches strictly forward — that monotonic

i

is the whole reason KMP is linear.

Because the inner while can run many times for a single value of

i

, the match loop is

O (nm)

in the worst case.

False. The while decrements

j

, and

j

only ever rose by

\leq n

total, so all while steps summed across all

i

number

\leq n

— this is an amortized

O (n)

, not per-

i

KMP requires extra space proportional to the text length

n

False. It stores only the

π

array of length

m

(plus two pointers), so auxiliary space is

O (m)

, independent of

n

j = m

(a full match) and we set

j = π [m - 1]

, we might report the same index twice.

False. After reporting,

i

still advances before the next possible report, and

j = π [m - 1]

realigns to a strictly earlier prefix, so no index is reported twice.

Spot the error

Each item is Buggy claim ::: What's actually wrong.

"On a mismatch, do j = π[j]."

Wrong index.

j

counts matched characters, so the last matched pattern index is

j - 1

; the border we need lives at

π [j - 1]

. Reading

π [j]

uses an unmatched or out-of-range slot.

"Define

π [i]

as the longest prefix=suffix, and allow the whole string to count."

Dropping proper breaks everything: the whole string is trivially the longest suffix, giving

π [i] = i + 1

, so

j = π [j - 1]

never shrinks and the fallback loops forever.

"After a full match set

j = 0

and restart."

You lose overlapping matches. In aaaa searching aaa, resetting to

0

misses the second occurrence;

j = π [m - 1]

keeps the reusable overlap.

"During the while fallback, keep testing while j >= 0."

Since

π

is only defined on indices

0.. m - 1

, index

- 1

is out of bounds — so when

j

hits

0

there is no border left and

π [j - 1] = π [- 1]

would read past the array; the guard must be while j > 0. At

j = 0

we simply compare

S [i]

with

S [0]

and stop falling back.

"When building

π

, compare

S [i]

against

S [i - 1]

We compare

S [i]

against

S [j]

where

j = π [i - 1]

is the current border length. Comparing against

S [i - 1]

ignores the whole border-chain idea and computes something meaningless.

"The failure function tells you where the next match starts in the text."

It does not point into the text at all.

π

is defined purely on the pattern; it tells you how many pattern characters stay valid after a slip, i.e. the new value of

j

"KMP's fallback jumps to the second-longest border by scanning all borders each time."

There is no scan. The next border after the length-

j

one is exactly

π [j - 1]

(the longest border of the border), so each fallback is a single

O (1)

lookup down the nested-border chain.

Why questions

Each item is Why…? ::: Reason.

Why does the border of a border give the next candidate when we fall back?

Any border shorter than the current one must itself be both a prefix and suffix of the current border, so the longest such is precisely

π [j - 1]

— nested borders form a decreasing chain we walk down.

Why is it safe not to re-read the text characters after a fallback?

The prefix

P [0.. π [j - 1] - 1]

is guaranteed equal to text we already matched (it's a border of the matched region), so re-comparing it would only re-confirm known equalities — pure waste.

Why does KMP still work when the pattern has no repeated structure (all borders length 0)?

Then every

π [i] = 0

, so each mismatch drops

j

straight to

0

; the algorithm degrades gracefully to "compare

P [0]

against

T [i]

" and stays linear.

Why do we build

π

over the pattern and not over the text?

The reusable overlaps depend only on the pattern's internal repetitions; the text is unknown/streaming, and precomputing on it would not generalize and would cost

O (n)

we can't reuse across queries.

Why is

j = π [j - 1]

preferred over sliding the pattern by one character?

π [j - 1]

is the longest safe overlap, so we slide the minimum distance — sliding by one more than that could skip past a genuine occurrence.

Why can we treat

π

construction as "matching the pattern against itself"?

Building

π

runs the same match machine with the pattern playing both roles; that's why the same amortized argument gives

O (m)

for it as gives

O (n)

for matching.

Why does the amortized argument use

j

as a potential rather than counting inner iterations directly?

j

is a single nonnegative quantity that rises by

\leq 1

per outer step and falls by

\geq 1

per inner step; bounding total rise (

\leq n

) instantly bounds total fall, sidestepping the impossible per-

i

count.

Edge cases

Each item is Situation ::: What happens / correct behaviour.

Empty pattern (

m = 0

The

π

array is empty and the match loop never advances

j

; by the standard convention an empty pattern matches at every start index

0

through

n

inclusive (there are

n + 1

such positions).

Pattern longer than text (

m > n

No occurrence is possible; the match loop finishes with

j

never reaching

m

, correctly reporting nothing in

O (n + m)

time.

Single-character pattern (

m = 1

π = [0]

; the match loop just checks

T [i] = P [0]

each step and reports every equal position — KMP reduces to a plain linear scan, which is optimal.

Pattern equal to the whole text (

P = T

One match is reported at index

0

;

j

reaches

m

exactly once at the end, then

j = π [m - 1]

has nothing further to match.

Text = aaaa...a, pattern = aaa.

Every window matches; overlapping occurrences at

0, 1, 2, \dots

are all found because

j = π [m - 1] = m - 1

after each report keeps almost all characters — this is exactly the situation drawn in the third figure above.

Text = aaaa...ab, pattern = aaa...ab (the classic naive killer).

This is exactly the

O (nm)

trap for naive matching, yet KMP stays

O (n + m)

because the amortized fallback bound doesn't depend on how adversarial the input looks. See also Z-algorithm and Rabin-Karp for alternative linear approaches.

Mismatch on the very first pattern character (

j = 0

T [i] \neq = P [0]

The while guard j>0 is already false, so nothing falls back; we just advance

i

, keeping

j = 0

— the degenerate case is handled by the guard, not a special branch.

Reaching a full match at the last text index (

i = n - 1

j = m

The match is reported normally, then

j = π [m - 1]

; since the for loop is about to end, no further comparisons occur — no out-of-bounds read of the text.

Recall Quick self-check anchors

If you missed several "Why questions", re-read the amortized proof; those hinge on the potential argument (second figure). If you missed "Spot the error" items, the culprit is almost always the $π [j - 1]$ vs $π [j]$ off-by-one. This machinery generalizes: Aho-Corasick runs the same failure-link idea over a whole trie of patterns.