Prefix Function, KMP, and Z Algorithm

Define the prefix function, show how borders are reused, build the failure table, process text in linear time, and compare KMP with the Z algorithm.

Prefix function π[i]: the length of the longest proper prefix of s[0..i] that is also a suffix of it (a border).

Z function z[i]: the length of the longest substring starting at i that matches a prefix of s.

Output (g++ 11.2, -std=c++17, warnings as errors, AddressSanitizer + UndefinedBehaviorSanitizer; Ubuntu 22.04 on WSL2):

The fallback k = π[k−1] reuses work: after matching k characters, the next candidate alignment is the longest border of what already matched. Each text character raises k by at most one, and every fallback lowers it, so there are at most n fallbacks in total and the search is O(n) plus O(m) to build the table. The run counted 29 900 character comparisons (the counter includes the comparison that ends each fallback) on the input that cost the naive search 990 100.

Output (CPython 3.13.1):

#include <bits/stdc++.h>
using namespace std;

vector<int> prefixFunction(const string& s) {
    vector<int> pi(s.size(), 0);
    for (size_t i = 1; i < s.size(); ++i) {
        int k = pi[i - 1];
        while (k > 0 && s[i] != s[k]) k = pi[k - 1];     // fall back to the next shorter border
        if (s[i] == s[k]) ++k;
        pi[i] = k;
    }
    return pi;
}
vector<int> zFunction(const string& s) {
    int n = (int)s.size(); vector<int> z(n, 0);
    for (int i = 1, l = 0, r = 0; i < n; ++i) {
        if (i < r) z[i] = min(r - i, z[i - l]);          // reuse the box [l, r) that matches a prefix
        while (i + z[i] < n && s[z[i]] == s[i + z[i]]) ++z[i];
        if (i + z[i] > r) { l = i; r = i + z[i]; }
    }
    return z;
}
vector<int> kmpSearch(const string& text, const string& pat, long long& cmps) {
    vector<int> pi = prefixFunction(pat), hits; int k = 0;
    for (size_t i = 0; i < text.size(); ++i) {
        while (k > 0 && (++cmps, text[i] != pat[k])) k = pi[k - 1];
        if ((++cmps, text[i] == pat[k])) ++k;
        if (k == (int)pat.size()) { hits.push_back(int(i) - k + 1); k = pi[k - 1]; }
    }
    return hits;
}

int main() {
    string p = "ababaca";
    aut
…

s : a b a b a c a 
pi: 0 0 1 2 3 0 1 
z(aabxaab): 0 1 0 0 3 1 0 
"ababaca" found at: 2 9
KMP on the naive search's worst case (n=10000, m=100): 29900 comparisons
Z-based matches: 2 9

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

def kmp_search(text, pat):
    pi, k, hits = prefix_function(pat), 0, []
    for i, c in enumerate(text):
        while k and c != pat[k]:
            k = pi[k - 1]
        if c == pat[k]:
            k += 1
        if k == len(pat):
            hits.append(i - k + 1)
            k = pi[k - 1]
    return hits

print(prefix_function("ababaca"), kmp_search("abababacaababaca", "ababaca"))

[0, 0, 1, 2, 3, 0, 1] [2, 9]

Quiz

? For s = "ababaca", what is π[4] (s[0..4] = "ababa")?
+ 3 :: "aba" is both a proper prefix and a suffix.
- 2 :: "ab" is not a suffix of "ababa".
- 5 :: Proper prefixes exclude the whole string.
- 1 :: "a" is a border, but not the longest.

? Why is KMP linear in the text length?
+ k rises at most once per character and each fallback lowers it, so total work is O(n + m). :: 29 900 counted comparisons in the run, against 990 100 for the naive method.
- It skips characters. :: It reads every text character once.
- It hashes the pattern. :: That is Rabin–Karp.
- It sorts the text. :: No.

? How does the Z algorithm find a pattern P in text T?
+ Compute z on P + "#" + T; positions with z = |P| are matches :: The separator stops matches crossing into T.
- Compute z on T only :: Needs the pattern.
- Compute z on T + P :: The order matters.
- It cannot :: It can.