PyInfo
String Algorithms contents

Prefix Function and Knuth-Morris-Pratt

Compute the longest proper border of every prefix in O(n), and use it for pattern matching, string periods and counting occurrences.

Intermediate6 min readprefix functionkmpborderspattern matching

Read first: Strings

For a string ss of length nn, the prefix function π[i]\pi[i] is the length of the longest proper prefix of s[0..i]s[0..i] that is also a suffix of s[0..i]s[0..i]. "Proper" means it is not the whole substring itself. Prefix-suffix pairs like this are called borders.

For "abcabcd":

ii 0 1 2 3 4 5 6
s[i]s[i] a b c a b c d
π[i]\pi[i] 0 0 0 1 2 3 0

For instance π[5]=3\pi[5] = 3 because "abc" is both a prefix and a suffix of "abcabc".

Computing it in O(n)O(n)

Compute π[i]\pi[i] from π[i−1]\pi[i-1]. Let k=π[i−1]k = \pi[i-1] be the length of the current border. If s[k]=s[i]s[k] = s[i], the border extends: π[i]=k+1\pi[i] = k + 1. If not, we fall back to the next shorter border, which is π[k−1]\pi[k-1], and try again, until k=0k = 0.

The total number of fall-backs is bounded by the total number of extensions (each fall-back strictly decreases kk, and kk grows by at most 1 per step), so the algorithm is linear.

python
def prefix_function(s):
    n = len(s)
    pi = [0] * n
    for i in range(1, n):
        k = pi[i - 1]
        while k > 0 and s[i] != s[k]:
            k = pi[k - 1]
        if s[i] == s[k]:
            k += 1
        pi[i] = k
    return pi

assert prefix_function("abcabcd") == [0, 0, 0, 1, 2, 3, 0]
assert prefix_function("aabaaab") == [0, 1, 0, 1, 2, 2, 3]
assert prefix_function("aaaa") == [0, 1, 2, 3]
assert prefix_function("") == []

def prefix_function_naive(s):
    return [
        max((k for k in range(i + 1) if s[:k] == s[i + 1 - k : i + 1]), default=0)
        for i in range(len(s))
    ]

import random
random.seed(1)
for _ in range(300):
    t = "".join(random.choice("ab") for _ in range(random.randint(0, 25)))
    assert prefix_function(t) == prefix_function_naive(t)

Pattern matching (KMP)

To find pattern tt in text ss, compute the prefix function of t + "#" + s, where # is a separator that occurs in neither string. Every position ii with π[i]=∣t∣\pi[i] = |t| marks an occurrence that ends at ii inside the combined string.

python
def kmp_search(s, t):
    """Start positions of every occurrence of t in s, in O(|s| + |t|)."""
    if not t:
        return list(range(len(s) + 1))
    pi = prefix_function(t + "\0" + s)                 # "\0" is assumed not to occur
    m = len(t)
    return [i - 2 * m for i in range(2 * m, len(pi)) if pi[i] == m]

assert kmp_search("abracadabra", "abra") == [0, 7]
assert kmp_search("aaaaa", "aa") == [0, 1, 2, 3]
assert kmp_search("hello", "xyz") == []

def naive_find(s, t):
    return [i for i in range(len(s) - len(t) + 1) if s[i : i + len(t)] == t]

for _ in range(300):
    text = "".join(random.choice("ab") for _ in range(random.randint(0, 30)))
    pat = "".join(random.choice("ab") for _ in range(random.randint(1, 5)))
    assert kmp_search(text, pat) == naive_find(text, pat)

Only O(∣t∣)O(|t|) extra memory is really needed if you process the text online instead of building the concatenation, which is helpful for streams.

Applications

Smallest period of a string

The string ss has a period pp if s[i]=s[i+p]s[i] = s[i+p] for all valid ii. The smallest period is n−π[n−1]n - \pi[n-1]. It divides the length exactly when the string is a repetition of a shorter block:

python
def shortest_repeating_block(s):
    n = len(s)
    if n == 0:
        return ""
    p = n - prefix_function(s)[-1]
    return s[:p] if n % p == 0 else s

assert shortest_repeating_block("abcabcabc") == "abc"
assert shortest_repeating_block("abcabca") == "abcabca"     # period 3 but does not divide 7
assert shortest_repeating_block("aaaa") == "a"
assert shortest_repeating_block("abab") == "ab"

Number of occurrences of each prefix

Every prefix of length π[i]\pi[i] ending at ii is also a suffix, which tells us how often each prefix occurs as a substring. Count the values of π\pi, then push the counts down the chain of borders (a border of length kk implies a border of length π[k−1]\pi[k-1]):

python
def prefix_occurrences(s):
    """occ[k] = number of occurrences of the prefix of length k in s (k = 1..n)."""
    n = len(s)
    pi = prefix_function(s)
    occ = [0] * (n + 1)
    for v in pi:
        occ[v] += 1
    for k in range(n - 1, 0, -1):
        occ[pi[k - 1]] += occ[k]
    return [c + 1 for c in occ[1:]]                    # +1: the prefix itself

assert prefix_occurrences("abab") == [2, 2, 1, 1]      # a x2, ab x2, aba x1, abab x1
for _ in range(100):
    t = "".join(random.choice("ab") for _ in range(random.randint(1, 15)))
    expected = [sum(t[i : i + k] == t[:k] for i in range(len(t) - k + 1)) for k in range(1, len(t) + 1)]
    assert prefix_occurrences(t) == expected

All borders of a string

Following π[n−1]→π[π[n−1]−1]→⋯\pi[n-1] \to \pi[\pi[n-1]-1] \to \cdots enumerates every border, longest first:

python
def all_borders(s):
    pi = prefix_function(s)
    out, k = [], pi[-1] if pi else 0
    while k > 0:
        out.append(k)
        k = pi[k - 1]
    return out

assert all_borders("abacaba") == [3, 1]                # "aba" and "a"
assert all_borders("abc") == []

The Z-function is a close cousin with the same applications, and either can be converted into the other in O(n)O(n).

Practice problems