Knuth–Morris–Pratt

Brute-force search wasted effort by forgetting the matches made before a mismatch. Rabin–Karp reduced this waste with a hash but never used the pattern’s structure at all.

The idea of the Knuth–Morris–Pratt algorithm is this: if the matched part is already known, the pattern’s own internal repetition tells us how many positions can safely be skipped.

The Observation

Consider comparing the pattern ABABCABAB against the text, where the first four characters (ABAB) matched and the fifth did not. It is known for certain that the text contains ABAB at that position.

Brute force shifts by one position and tests the text’s BAB… portion from scratch. Yet the AB prefix of ABAB is also its AB suffix; the search can therefore continue after shifting by two positions, without retesting the pattern’s first two characters. The intermediate positions are not worth trying, because what characters are there is already known.

The general rule: the longest piece that is both a prefix and a suffix of the matched prefix is kept, the rest is discarded.

The Prefix Function

The prefix function $\pi$ gives, for every prefix of the pattern, “the length of the longest piece that is both a proper prefix and a suffix.” “Proper” here means the piece cannot be the whole prefix itself.

def prefix_function(pattern: str) -> list[int]:
    """pi[i]: the longest proper prefix-suffix length of pattern[0..i]."""
    pi = [0] * len(pattern)
    k = 0
    for i in range(1, len(pattern)):
        while k > 0 and pattern[i] != pattern[k]:
            k = pi[k - 1]                  # fall back to a shorter candidate prefix
        if pattern[i] == pattern[k]:
            k += 1
        pi[i] = k
    return pi


print(prefix_function("ABABCABAB"))       # [0, 0, 1, 2, 0, 1, 2, 3, 4]
print(prefix_function("AABAACAABAA"))     # [0, 1, 0, 1, 2, 0, 1, 2, 3, 4, 5]
print(prefix_function("ABCDE"))           # [0, 0, 0, 0, 0]

The values read directly: the longest prefix–suffix overlap of the entire pattern ABABCABAB is 4 (ABAB); for the ABAB piece up to its fourth character it is 2 (AB); for ABCDE, which contains no repetition at all, every value is zero.

The computation itself is searching the pattern within itself: the variable k holds the length of the prefix matched so far and falls back to a shorter candidate on a mismatch. The cost is $O(m)$ — the reasoning is the same as in the search, and is given in the next section.

The Search

The search applies the same fallback logic to the text. The text cursor never moves backward; only the pattern cursor falls back.

def kmp(text: str, pattern: str) -> tuple[list[int], int]:
    """(positions, character-comparison count)"""
    pi = prefix_function(pattern)
    positions: list[int] = []
    k = 0
    count = 0
    for i, character in enumerate(text):
        while k > 0 and character != pattern[k]:
            count += 1
            k = pi[k - 1]
        count += 1
        if character == pattern[k]:
            k += 1
        if k == len(pattern):
            positions.append(i - len(pattern) + 1)
            k = pi[k - 1]                  # do not miss an overlapping next occurrence
    return positions, count


text = "ABABDABACDABABCABAB"
pattern = "ABABCABAB"
print(kmp(text, pattern))                  # ([10], 23)
print(kmp("ABABAB", "AB"))                 # ([0, 2, 4], 6)
print(kmp("A" * 30 + "B", "A" * 10 + "B")) # ([20], 51)

The last line is decisive: on the input where brute force made 231 comparisons, KMP makes 51. The quadratic behavior has disappeared entirely.

Once a match is found, the assignment k = pi[k-1] ensures overlapping occurrences are not missed. Searching for ABAB inside ABABAB finds both position 0 and position 2.

Cost

Preprocessing is $O(m)$, search is $O(n)$, total $O(n + m)$ — in the worst case. Extra space is $O(m)$ (the prefix-function table).

The reasoning is amortized; the total-cost method from the Method for Computing Complexity lesson applies here directly.

The variable k increases by at most one on every turn; over $n$ turns, its total increase is at most $n$. Every turn of the inner loop decreases k by at least one, and k never goes negative. The inner loop can therefore run at most $n$ times in total. Although the inner loop looks like $O(m)$ in isolation, its total cost across the whole search is linear.

Criterion	Brute force	Rabin–Karp	KMP
Preprocessing	None	$O(m)$	$O(m)$
Worst-case search	$O(nm)$	$O(nm)$	$O(n)$
Extra space	$O(1)$	$O(1)$	$O(m)$
Backtracks in text	Yes	No	No

The last row produces a practical consequence: because the text cursor never moves backward, the algorithm can run over a stream that is not entirely in memory. Characters are processed as they arrive; no rewinding is needed.

The Automaton View

The prefix function is, in fact, a compressed form of a finite automaton. Its states hold the information “how many characters of the pattern have matched so far”; a transition is defined for every character, and the final state signals a match.

If the transitions are precomputed, the fallback loop disappears from the search as well: exactly one table lookup is made for every text character.

def automaton(pattern: str, alphabet: str) -> list[dict[str, int]]:
    pi = prefix_function(pattern)
    m = len(pattern)
    transition: list[dict[str, int]] = [{} for _ in range(m + 1)]
    for state in range(m + 1):
        for character in alphabet:
            if state < m and character == pattern[state]:
                transition[state][character] = state + 1      # advance
            elif state == 0:
                transition[state][character] = 0              # back to start
            else:
                transition[state][character] = transition[pi[state - 1]][character]
    return transition


def search_with_automaton(text: str, pattern: str, alphabet: str) -> list[int]:
    transition = automaton(pattern, alphabet)
    m, state = len(pattern), 0
    positions: list[int] = []
    for i, character in enumerate(text):
        state = transition[state][character]
        if state == m:
            positions.append(i - m + 1)
    return positions


print(search_with_automaton("ABABDABACDABABCABAB", "ABABCABAB", "ABCD"))    # [10]

The cost is in memory: the table takes $O(m\sigma)$ space, and this is a serious cost when the alphabet is large. The prefix function, by contrast, takes $O(m)$ space and produces the same behavior amortized. The choice between the two approaches is made by looking at alphabet size and search frequency.

Periodicity

The prefix function directly gives one more piece of information besides the search: a string’s smallest period.

For a string of length $m$, the value $p = m - \pi[m-1]$ is the smallest period length. If $m$ is exactly divisible by $p$, the string consists of repetitions of that piece.

def smallest_period(string: str) -> tuple[int, bool]:
    pi = prefix_function(string)
    p = len(string) - pi[-1]
    return p, len(string) % p == 0


for example in ("ABABAB", "ABCABCABC", "ABCD", "AAAA"):
    print(example, smallest_period(example))

# ABABAB (2, True)
# ABCABCABC (3, True)
# ABCD (4, True)
# AAAA (1, True)

For ABCD the period is the length itself: there is no repetition. This computation is used in compression and in string-equivalence questions; the same table serves two different purposes.

Summary

• KMP uses the prefix–suffix overlap of the matched prefix to determine how many positions can be skipped on a mismatch.
• The prefix function gives, for every prefix, the longest proper prefix–suffix length, and is computed in $O(m)$.
• In the search, the text cursor never moves backward; only the pattern cursor falls back.
• Total cost is $O(n + m)$; the reasoning is amortized, bounding the total increase of the variable k.
• The absence of backtracking in the text makes the algorithm suitable for stream data.
• The same table also gives a string’s smallest period.

Next Step

KMP matches the pattern from start to end and looks at every text character at least once. The next lesson takes up an approach that matches in the opposite direction: comparison starting from the end of the pattern makes it possible to skip over some text characters without ever looking at them on a mismatch, and produces sublinear behavior in practice.