A text search often discovers that the beginning of a pattern matches several characters, then fails on the next one. Restarting at the next text position throws away information: some suffix of the matched part may already be another valid pattern prefix. KMP records exactly these reusable prefixes.
The main idea is not simply to move an index backward more quickly. Every fallback must preserve a precise statement about characters already read. We will derive the fallback rule from borders, prove why the total comparison work is linear, and explain the reset needed to report overlapping occurrences.
A border is simultaneously a prefix and a suffix
Definition 9.1.1
(Proper border and prefix function)
For a nonempty word of length , a proper border is a prefix that is also a suffix and has length strictly smaller than . The empty word, of length zero, is allowed.
For a pattern indexed from zero, define as the length of the longest proper border of the prefix . Thus , and .
All indices and reported match positions in this section are zero-based. In Python notation, is P[:i + 1].
For ababa, the nonempty proper borders are a and aba, with lengths 1 and 3. The whole word is a prefix and suffix too, but it is excluded by “proper.” Neither ab nor abab is a suffix. A border is an equality of whole substrings, not merely an equality of their first or last character.
Lemma 9.1.2
(Borders of a border)
Let be a proper border of a word , of length . For every , the number is a border length of if and only if it is a border length of . Consequently, for a pattern the sequence , continued while the entries are positive, lists all proper border lengths of in decreasing order, followed by .
Proof
(Shorter borders sit inside the longest border)
Let be a border of of length . For any , the length- prefix of equals the length- prefix of , because is a prefix. The length- suffix of equals the length- suffix of , because is also a suffix.
Consequently, is a border length of if and only if it is a border length of . In particular, after the longest border of length , the next possible smaller border is the longest proper border of that border.
Since a pattern border of length is the word P[:j], its longest proper border has length . Repeatedly following these values lists all smaller border lengths in decreasing order, ending at zero.
Build the prefix function by extending an existing border
Suppose are known. Let . The previous prefix already ends with P[:j]. If the new character equals , that border extends to length .
If the characters differ, a shorter previous border might still extend. The border lemma identifies the next candidate as . Repeat until an extension succeeds or . At zero, compare against ; a match gives length one, and a mismatch gives length zero.
Theorem 9.1.3
(Prefix-function recurrence)
For , let and while , so the chain ends at . Then for the first in this chain with , and if no entry of the chain has .
Proof
(The first successful extension is the longest)
Any nonempty proper border of , of length , becomes a border of the previous prefix after its final character is removed. That previous border has length . Its final extension must compare with .
The algorithm begins with the longest previous border and follows the complete descending chain of smaller ones. Every failed candidate is ruled out by the required character comparison. The first successful candidate therefore gives the largest possible new border. If none extends, only the empty border remains. This proves the recurrence by induction over .
Worked example 9.1.4
(A mismatch can require several border fallbacks)
For pattern ababaca, the table is
| Index | |||||||
|---|---|---|---|---|---|---|---|
| Character | a | b | a | b | a | c | a |
Before index 5, the prefix ababa has longest border aba, of length 3. The new c does not match , so fall back to . It also does not match , so fall back to . It does not match either, giving .
The candidate lengths are . They are the actual border lengths of the previously matched word. The following a then starts a new border of length one.
Carry the same invariant through the text
Let the pattern have length and the text length . Between text characters, keep equal to the length of the longest pattern prefix of length strictly less than that is a suffix of the text consumed so far. Initially .
For the next text character, compare it with . On a mismatch with , replace by and try again against the same text character. On a match, increment . A mismatch at zero leaves zero.
If , a full occurrence has just ended at text index , so its start is . Report it, then set before reading the next text character.
Theorem 9.1.5
(Scan invariant and reported occurrences)
With the mismatch fallback and the full-match reset above, is, between text characters, the length of the longest pattern prefix of length less than that is a suffix of the consumed text, and every occurrence is reported exactly once, when its last character is read.
Proof
(Fallback and reset keep exactly the useful suffix)
Before the new character, the matched suffix is P[:j]. Any shorter pattern prefix that also suffixes the consumed text must be a border of that matched word. The border chain therefore enumerates every possible shorter state without rereading earlier text characters.
After a successful extension, all longer candidates have already failed, so the new gives the longest matching prefix. If its length is , the consumed text ends with the full pattern, which proves the reported occurrence. To continue, the longest shorter pattern prefix that suffixes this occurrence is exactly its longest proper border, of length .
This restores the between-character invariant, including after a reported occurrence. Every possible match endpoint is examined, so no occurrence is omitted. The reset retains the suffix that may begin an overlapping occurrence.
Proof X-ray
Where the border lemma is used twice
The same lemma carries the invariant through two different moves. On a mismatch, the fallback walks down the borders of the matched word P[:j], which are exactly the shorter candidate states, so no state is skipped. After a full match the word read is the whole pattern, whose longest proper border has length ; resetting to it keeps the longest suffix that can begin another occurrence, whereas resetting to zero would drop it. After each fallback the same text character is compared again, so a candidate is discarded only because its next character failed, never because its length was small.
Worked example 9.1.6
(Overlapping matches require retaining a border)
Search for aaa in aaaaa. Its prefix table is [0, 1, 2]. At text index 2 a full match starts at 0. Reset to : the last two characters already match aa.
The next a completes another occurrence starting at 1. The same reset lets the final a complete one starting at 2. The output is [0, 1, 2]. Resetting to zero after the first occurrence would discard those overlapping starts.
Likewise, aba occurs in ababa at positions [0, 2]. Its final border a carries information from the end of one occurrence into the next.
An arbitrary decrement can create a false match
Counterexample mode
Replacing the fallback by j minus one breaks the invariant
Take pattern ababc and text ababbc. After reading the first four characters abab, the matched length is 4. The next text character is b, which mismatches the expected c.
A faulty fallback to length 3 would claim that aba is a suffix of the already read abab, although its actual length-three suffix is bab. The current b then matches pattern position 3, and the final c appears to finish a full match. The faulty algorithm reports start 1, whose text window is babbc, not ababc.
The correct fallback is ; neither state extends on this b. No occurrence is reported. A fallback is justified by substring equality, not merely by a smaller numeric index.
The explorer replays methods from the practice questions below, including the false-match example above. Try those questions first for independent practice. Select the false-match example, search view and decrement rule to inspect the invalid fallback.
Bound the total work, not the work of one character
One character can trigger several fallbacks. That does not make the whole algorithm quadratic.
Theorem 9.1.7
(Linear total work of KMP)
With constant-time symbol comparisons, prefix preprocessing takes time and the text scan takes time, so searching takes time plus to output matches.
Proof
(Counting decreases against increases)
During prefix preprocessing, the current matched length increases by at most one per outer iteration. Every fallback decreases it by at least one, and it never becomes negative. Starting from zero, the total number of fallback iterations cannot exceed the total increases, which are at most the pattern length.
The text scan has the same accounting. Each text character can increase at most once. Mismatch fallbacks and full-match resets only decrease it. Thus there are at most linearly many mismatch-loop iterations across the whole text. Apart from these, each outer iteration makes only a constant number of comparisons.
Preprocessing takes time and searching takes time, assuming constant-time symbol comparisons. Returning matches adds output work and storage. The prefix table uses working space; the match list is additional output space. Since there are at most starts including the empty-pattern case, total time is .
Proof X-ray
The potential that pays for every fallback
Take as the potential. It starts at , is never negative, and grows by at most per outer iteration. A fallback replaces by , and because a proper border is shorter than its word, so every fallback lowers by at least . The number of fallbacks is therefore at most the total growth: at most in the scan and at most in preprocessing. The bound is amortized: a single character may trigger many fallbacks, but only after earlier characters have raised that high.
Common mistake
(Linear time is not one comparison per character)
This argument does not say each text character is compared only once. The text index never moves backward, but the current character may be compared against several pattern positions. The aggregate bound is what makes the search linear.
A complete implementation, including the empty pattern
We use the convention that an empty pattern occurs at every text boundary, including before the first and after the last character. This gives positions and is handled separately to avoid indexing an empty pattern.
def prefix_function(pattern):
pi = [0] * len(pattern)
for i in range(1, len(pattern)):
j = pi[i - 1]
while j > 0 and pattern[i] != pattern[j]:
j = pi[j - 1]
if pattern[i] == pattern[j]:
j += 1
pi[i] = j
return pi
def kmp_find_all(text, pattern):
if not pattern:
return list(range(len(text) + 1))
pi = prefix_function(pattern)
matches = []
j = 0
for i, symbol in enumerate(text):
while j > 0 and symbol != pattern[j]:
j = pi[j - 1]
if symbol == pattern[j]:
j += 1
if j == len(pattern):
matches.append(i - len(pattern) + 1)
j = pi[j - 1]
return matches
The full-match check resets before the next iteration, so pattern[j] is always within bounds when compared. If the pattern is longer than the text, the scan simply cannot reach its full length. No special separator character or concatenated pattern-text string is required.
Common mistake
(Falling back with instead of )
After a mismatch in state , the matched word is P[:j], whose longest proper border has length . The value belongs to the longer prefix P[:j+1], which contains the character that just failed. For pattern ababc and text abababc, the correct scan reaches after abab, mismatches on a, falls back to and reports the occurrence at . Using drops the border ab and misses it.
The longest border also reveals the minimum period
Definition 9.1.8
(Period of a word)
For a nonempty word of length , a positive integer is a period if for every . A border of length is exactly the statement that the first characters equal the last , which is the period condition for .
Theorem 9.1.9
(Minimum period from the longest border)
For a nonempty word of length , the smallest positive period of is
Proof
(Periods correspond to borders)
By the correspondence above, is itself a period. Every other period would give a border of length , no larger than the longest border, so .
A period need not divide the word length. ababa has period 2 despite length 5. If the period does divide , the word consists of complete repetitions of its first period-length block; for example ababab repeats ab three times.
Worked example 9.1.10
(Minimum periods, including a word with no border)
For abcabcab the prefix table is , so and : the word is the block abc repeated, ending with the partial block ab. For abc the table is and : there is no nonempty proper border, so the only period is the whole word length. For aaaa the table is and .
Exercises and worked solutions
Quick check
(1. Identify genuine proper borders)
List all proper border lengths of ababa, including zero. Why are lengths 2, 4 and 5 excluded?
Solution · Solution 1
The lengths are 0, 1 and 3. The corresponding nonempty words are a and aba. The length-two prefix ab differs from suffix ba; the length-four prefix abab differs from suffix baba. Length five is excluded because a proper border cannot be the whole word.
Quick check
(2. Follow actual border links)
For ababaca, what is the current matched border just before processing c? Give the fallback lengths and the final prefix value at that index.
Solution · Solution 2
The preceding prefix ababa has longest border aba, of length 3. The chain is . Character c extends none of these states, so .
Quick check
(3. Preserve overlapping starts)
After the first match of aaa in aaaaa, what state is retained and why? Give every match position. What goes wrong if the state is reset to zero?
Solution · Solution 3
Retain state 2, the length of border aa. The match positions are 0, 1 and 2. Resetting to zero discards the two already matched suffix characters, so the remaining text cannot reveal those overlapping length-three occurrences under that faulty scan.
Quick check
(4. Diagnose a false fallback state)
In the ababc/ababbc counterexample, why is length 3 an invalid state after the first mismatch? Which text window would the faulty algorithm eventually report?
Solution · Solution 4
The consumed abab ends with bab, not pattern prefix aba, so length 3 does not describe a true suffix match. The faulty extension later reports window babbc at start 1. Its unequal content shows this is a false positive, not merely an inefficient search.
Quick check
(5. Explain linear total comparisons despite repeated failures)
Suppose one text character causes several fallback-loop iterations. Which quantity decreases, and what earlier work limits the total number of such iterations across the scan?
Solution · Solution 5
The matched-prefix length strictly decreases on every fallback. It starts at zero, never goes negative and increases at most once per text character. The total decreases therefore have only a linear budget supplied by earlier increases. Constant additional comparison work per text character keeps total search time linear.
Quick check
(6. Recover periods without assuming divisibility)
Use the longest-border formula to find the minimum period of ababab and ababa. Which word is an integer number of copies of the block ab, and why is the other still periodic under the definition?
Solution · Solution 6
Their longest borders have lengths 4 and 3, so both minimum periods are 2. ababab has length six and is three copies of ab. ababa has length five, but every character at index at least two still equals the character two positions earlier. The period condition permits a final partial block.