KMP and the Prefix Function

Intuition

String matching: find every position where a pattern p (length m) occurs in a text t (length n). The brute-force matcher tries every start and compares up to m characters, O(n * m) in the worst case (think t = "aaaa...ab", p = "aa...ab"). Its waste: after a mismatch it forgets everything it just matched.

KMP keeps that knowledge. Suppose j characters of the pattern matched and the next one fails. The matched part p[:j] is known text, so the next possible alignment is the longest proper prefix of p[:j] that is also its suffix, called its longest border. Slide the pattern so that this border lines up and continue; the text pointer never moves back.

The prefix function stores those borders: pi[i] = length of the longest proper prefix of s[:i + 1] that is also a suffix of it. For s = "abacaba", pi = [0, 0, 1, 0, 1, 2, 3] (the whole string ends with "aba", which is also how it starts).

Computing pi reuses itself: to extend the border at position i, try the current border j = pi[i - 1]; if s[i] != s[j], fall back to the next shorter border pi[j - 1], and so on. j grows by at most 1 per step and every fallback shrinks it, so the total work is linear.

When to use it in interviews / OAs

• Find the first or all occurrences of a needle (implement strStr), counting overlapping matches too.
• "Longest prefix that is also a suffix" (longest happy prefix): it is pi[-1].
• Periodicity: smallest period, "is the string some block repeated k >= 2 times?".
• "Shortest palindrome by adding characters in front": longest palindromic prefix via s + "#" + reverse(s).
• Matching in a stream: KMP consumes the text one character at a time and never rereads it.

If the interviewer only needs "does it occur", a rolling hash is shorter to write; KMP wins when you need guarantees (no collisions) or the border structure itself.

Template

Brute force baseline

def brute_search(text: str, pattern: str) -> list[int]:
    n, m = len(text), len(pattern)
    return [i for i in range(n - m + 1) if text[i:i + m] == pattern]  # O(n * m)

Prefix function and KMP search

def prefix_function(s: str) -> list[int]:
    pi = [0] * len(s)
    for i in range(1, len(s)):
        j = pi[i - 1]  # longest border of s[:i]
        while j > 0 and s[i] != s[j]:
            j = pi[j - 1]  # fall back to the next shorter border
        if s[i] == s[j]:
            j += 1
        pi[i] = j
    return pi


def kmp_search(text: str, pattern: str) -> list[int]:
    if not pattern:
        return list(range(len(text) + 1))
    pi = prefix_function(pattern)
    res, j = [], 0  # j = number of pattern characters matched so far
    for i, ch in enumerate(text):
        while j > 0 and ch != pattern[j]:
            j = pi[j - 1]
        if ch == pattern[j]:
            j += 1
        if j == len(pattern):
            res.append(i - j + 1)
            j = pi[j - 1]  # continue: occurrences may overlap
    return res

An equivalent one-liner idea: compute prefix_function(pattern + "#" + text) with a separator that occurs in neither string; every position where the value equals m ends an occurrence.

Borders, periods and palindromic prefixes

If s has a border of length b, then len(s) - b is a period (s[i] == s[i + p] for every valid i). The longest border gives the smallest period.

def smallest_period(s: str) -> int:
    return len(s) - prefix_function(s)[-1] if s else 0


def is_repeated(s: str) -> bool:
    # s == block * k for some k >= 2
    p = smallest_period(s)
    return p < len(s) and len(s) % p == 0


def longest_happy_prefix(s: str) -> str:
    return s[:prefix_function(s)[-1]] if s else ""


def shortest_palindrome(s: str) -> str:
    # longest palindromic prefix of s = longest border of s + "#" + reverse(s)
    rev = s[::-1]
    k = prefix_function(s + "#" + rev)[-1]  # "#" must not occur in s
    return rev[:len(s) - k] + s

Complexity

prefix_function is O(n) time and space; KMP search is O(n + m) time and O(m) extra space (only the pattern's pi is stored). The brute force is O(n * m) in the worst case.

Common pitfalls

• Off-by-one in pi. pi[i] describes the prefix ending at index i (length i + 1); after j matched characters the fallback is pi[j - 1], not pi[j].
• Not resetting after a full match. Without j = pi[j - 1], the next comparison reads pattern[m] and crashes, or you miss overlapping occurrences.
• Separator collisions. In pattern + "#" + text, the separator must not appear in either string, or borders can leak across it.
• Empty pattern. Decide what it should return (Python's find returns 0) and handle it before indexing pattern[0].
• Period vs. repetition. The smallest period p always exists, but the string is a full repetition only if p divides n and p < n ("abcab" has period 3 but is not a repetition).
• Confusing pi with the Z-function. pi[i] is about the substring ending at i; z[i] is about the substring starting at i.

Interview variations

• Repeated substring pattern. is_repeated(s); an alternative to the s in (s + s)[1:-1] trick, which is only linear if the substring search is.
• Rotation check. b is a rotation of a iff len(a) == len(b) and b occurs in a + a (run KMP).
• All borders. Follow pi[n - 1], pi[pi[n - 1] - 1], ... down to 0; each one is a prefix that is also a suffix.
• Count occurrences of every prefix of s inside s: add pi values into buckets and push counts from longer to shorter borders, O(n) in total.
• Shortest palindrome / longest palindromic prefix. The s + "#" + reverse(s) construction above.
• KMP automaton. Precomputing transitions for every (state, letter) pair supports DP over strings that must avoid a pattern; usually beyond interview scope.