KMPPrefix-function matching

01Why it exists

Reach for it when you see:Finding a pattern in a text with a guaranteed linear worst case, data arriving chunk by chunk with no going back, the longest string that is both a prefix and a suffix, the shortest period of a string, the overlap between the tail of one string and the head of another.

02The core idea

When brute-force matching hits a mismatch between T[i] and P[j], it shifts P one place to the right and backs i up to start over. The waste is this: before the mismatch it had already confirmed T[i−j..i−1] = P[0..j−1], so the content of that stretch of text is fully determined by P and there is no reason to look at T again. How far P can slide after a mismatch without skipping an answer therefore depends only on P, and can be worked out in advance. That is the idea behind KMP (Knuth–Morris–Pratt).

Suppose j characters have matched. If P can still succeed after sliding right, the start of P in its new position must equal the end of the matched stretch P[0..j−1] — in other words it must be a border of P[0..j−1]: a string that is both a proper prefix and a suffix. The smaller the shift, the longer the border it needs, so keeping the longest border gives the smallest feasible shift. Any smaller shift would need a longer border, none exists, and so none of the positions skipped over can be an answer. Define the prefix function pi[i] as the length of the longest border of P[0..i]. On a mismatch, set j = pi[j−1], leave i alone, and compare T[i] against the new P[j]; if that fails too, fall back again, until either a match happens or j reaches 0. With P = aabaaab, for example, having matched aabaa, whose longest border is aa, the pattern slides straight to the position where only that aa stays aligned.

Building the pi table uses the very same rule, just matching P against itself: j is the current border length, P[i] = P[j] extends the border by one, and otherwise you fall back to pi[j−1] and try again. The complexity needs amortised analysis: processing one character raises j by at most 1, each fallback lowers j by at least 1, and j never goes below 0, so the total number of fallbacks cannot exceed the total number of advances. Building costs O(m) and searching O(n), for O(n + m) together, and that is a worst-case guarantee, not an average. The only extra space is the pi table, O(m). Another common formulation takes pi over the whole concatenation of P, #, and T, where every position holding the value m marks an occurrence.

The usual traps: pi[0] is always 0 and the build loop must start at i = 1, or a segment gets counted as a border of itself; on a mismatch you look up pi[j−1], not pi[j]; the fallback needs a while loop rather than an if, since it may fall back several times in a row; and after a hit, j must be set to pi[m−1] rather than 0, or searching for aaa inside aaaaa misses the overlapping occurrences. The pi table is useful in its own right: the shortest period of a string is m − pi[m−1], and when that divides m, the string is exactly that period repeated. How this sits next to the neighbouring lessons: Rabin-Karp reaches expected linear time with hashing while KMP is deterministic; the Z-Algorithm, coming up next, records the common prefix between each position and the start instead, and solves very nearly the same set of problems; and with many patterns at once, moving the pi idea onto a trie gives you Aho–Corasick.

03The algorithm

1. 1Build the pi table: pi[0] = 0, j = 0; for i from 1 to m−1, while j > 0 and P[i] ≠ P[j] set j = pi[j−1]; if P[i] = P[j] increment j; finally pi[i] = j.
2. 2To search, set j = 0 and scan T from the start. For each T[i], while j > 0 and T[i] ≠ P[j], fall back to j = pi[j−1] while i stays put.
3. 3If T[i] = P[j], increment j; otherwise j is already 0 and you simply move on to the next character.
4. 4If j = m, record the occurrence at i − m + 1 and set j = pi[m−1] to keep looking for a possibly overlapping next one.
5. 5For periods and overlaps, just read pi: the shortest period is m − pi[m−1], and the longest overlap between the end of A and the start of B is the last cell of pi taken over B, #, A.

04Interactive demo

P = aabaaab, T = aabaabaaab. The first phase builds the pi table: the top row is P and the bottom row is a second copy of P aligned at position i − j, matching the pattern against itself. Green marks characters that match; yellow marks a mismatch that can still fall back, and the pi cell being consulted turns yellow at the same time; blue marks a mismatch where j is already 0. At i = 2 the fallback to j = 0 still does not match, so pi[2] = 0; at i = 5 the fallback to j = 1 does match, so pi[5] = 2. The finished table is pi = [0, 1, 0, 1, 2, 2, 3]. The second phase searches T: the first five characters aabaa all match, then T[5] = b mismatches P[5] = a. Brute force would shift P by one and restart from T[1]; KMP looks up pi[4] = 2, knows the matched aabaa begins and ends with aa, and slides P straight to position 3 with j = 2 while i stays where it is. T[5] = b then matches P[2], the rest matches all the way to the end, and P is found at position 3. Across the whole run, i moved forward exactly 10 steps.

05Code

Python has the prefix function, every occurrence including overlapping ones, and the shortest period derived from pi. C++ has a streaming matcher that keeps its state across chunks, showing that a boundary split across the seam is still found, plus the head-to-tail overlap of two sequences computed from pi.

def prefix_function(p):
    """pi[i]: length of the longest proper prefix of p[:i+1] that is also a suffix. O(m)"""
    pi = [0] * len(p)
    j = 0                                   # current border length
    for i in range(1, len(p)):              # start at 1: a segment is not a border of itself
        while j > 0 and p[i] != p[j]:
            j = pi[j - 1]                   # cannot extend, so fall back to a shorter border, maybe several times
        if p[i] == p[j]:
            j += 1
        pi[i] = j
    return pi


def kmp_search(text, pat):
    """Every position where pat occurs in text, overlaps included. O(n + m)"""
    if not pat:
        return []
    pi, res, j = prefix_function(pat), [], 0
    for i, ch in enumerate(text):           # i only ever moves forward, so text could be a stream
        while j > 0 and ch != pat[j]:
            j = pi[j - 1]
        if ch == pat[j]:
            j += 1
        if j == len(pat):
            res.append(i - j + 1)
            j = pi[j - 1]                   # do not reset to 0, or the next overlapping hit is missed
    return res


def min_period(s):
    """The smallest p for which s[i] == s[i + p] holds at every valid i"""
    return len(s) - prefix_function(s)[-1] if s else 0


if __name__ == "__main__":
    print(prefix_function("aabaaab"))           # [0, 1, 0, 1, 2, 2, 3]
    print(kmp_search("aabaabaaab", "aabaaab"))   # [3]
    print(kmp_search("aaaaa", "aaa"))            # [0, 1, 2]
    for s in ["abcabcabc", "abcabca"]:
        p = min_period(s)
        print(s, p, len(s) % p == 0)            # abcabcabc 3 True: built by repeating abc
                                                # abcabca 3 False: the period is 3, but the last copy is incomplete

06Practice

• LeetCode 28Find the Index of the First Occurrence in a StringEasy
• LeetCode 459Repeated Substring Pattern (the shortest period divides the length)Easy
• LeetCode 1764Form Array by Concatenating Subarrays of Another Array (KMP over an integer array)Medium
• LeetCode 1392Longest Happy Prefix (the answer is exactly pi[m−1])Hard
• LeetCode 214Shortest Palindrome (take pi over s, #, and s reversed)Hard
• LeetCode 3008Find Beautiful Indices in the Given Array II (two KMP passes, then two pointers)Hard