String Algorithms: Hashing, KMP and the Z-Function

Find every occurrence of a pattern in linear time, read periods off the prefix function, and compare substrings in O(1) with a rolling hash that is hard to break.

A pattern search that is slower than it looks

Here is a problem of the kind this lesson is about. A monitoring tool receives a long stream of characters, up to 10^6 of them, and a signature of up to 10^5 characters. It must report every position where the signature starts, and occurrences may overlap. The obvious solution tries each start position and compares characters until the first mismatch.

On ordinary text that loop is fast, because most attempts fail on the first or second character. The worst case is input that almost matches everywhere: a text of all a and a pattern of as ending in one b. Every attempt walks almost the whole pattern before it fails. This program counts the character comparisons on exactly that input, with the pattern half as long as the text:

main.cppc++23

#include <cstddef>
#include <print>
#include <string>

// Try every start position; compare until the first mismatch.
long long naiveCount(const std::string& text, const std::string& pat,
                     long long& comparisons) {
    long long hits = 0;
    for (std::size_t i = 0; i + pat.size() <= text.size(); ++i) {
        std::size_t k = 0;
        while (k < pat.size()) {
            ++comparisons;
            if (text[i + k] != pat[k]) break;
            ++k;
        }
        if (k == pat.size()) ++hits;
    }
    return hits;
}

int main() {
    std::println("{:>6} {:>6} {:>12} {:>5}", "n", "m", "comparisons", "hits");
    for (std::size_t n : {2'000, 4'000, 8'000, 16'000}) {
        std::size_t m = n / 2;
        std::string text(n, 'a');
        std::string pat(m - 1, 'a');
        pat += 'b';  // agrees with the text almost everywhere, matches nowhere
        long long comparisons = 0;
        long long hits = naiveCount(text, pat, comparisons);
        std::println("{:>6} {:>6} {:>12} {:>5}", n, m, comparisons, hits);
    }
}

Output

Press Run to compile and run this example.

     n      m  comparisons  hits
  2000   1000      1001000     0
  4000   2000      4002000     0
  8000   4000     16004000     0
 16000   8000     64008000     0

Doubling the input quadruples the work: the naive search is O(n·m) for a text of length n and a pattern of length m. With n = 10^6 and m = 10^5, that is up to about 10^11 comparisons, far beyond the rule-of-thumb budget from Complexity in Practice. Contest problem setters include such inputs on purpose; in an interview, the question "what is the worst case?" leads straight here.

This lesson gives you three linear-time tools. The prefix function (the heart of the Knuth-Morris-Pratt algorithm) and the Z-function are exact and deterministic. The rolling hash is probabilistic but more flexible: once built, it compares any two substrings in O(1). All three are short enough to write from memory, and each is stress tested here against a slow reference.

Borders: what a partial match already tells you

The naive search throws information away. Suppose the pattern is abacab and we have matched abaca before a mismatch. We know the last five characters of the text are abaca. Sliding the pattern by one position and comparing again repeats work whose result we already know.

The useful question is: after a mismatch, how far back can the match restart without missing an occurrence? The answer depends only on the pattern, through its borders.

A border of a string is a proper prefix that is also a suffix. The string abacaba has the borders a (length 1) and aba (length 3); abacaba itself does not count because a border must be proper. The prefix function of a string s is the array pi where pi[i] is the length of the longest border of the prefix s[0..i].

Work it out by hand for s = abacaba:

`i`	prefix	longest border	`pi[i]`
0	`a`	(none)	0
1	`ab`	(none)	0
2	`aba`	`a`	1
3	`abac`	(none)	0
4	`abaca`	`a`	1
5	`abacab`	`ab`	2
6	`abacaba`	`aba`	3

Two facts make pi cheap to compute. First, pi[i] is at most pi[i - 1] + 1: a border of s[0..i] with its last character removed is a border of s[0..i-1]. So the candidate for position i is to extend the previous border by one character. Second, if that fails, the next candidate is not "one shorter" but the longest border of the border, which is pi[j - 1] when the current border has length j. The borders of a string form a chain j, pi[j - 1], pi[pi[j - 1] - 1], ... down to 0, and we walk that chain until a border extends or we reach zero.

KMP uses the same idea to scan the text. It keeps j, the number of pattern characters matched so far. On a match j grows by one; on a mismatch j falls back along the border chain of the pattern. The text pointer never moves backwards.

The prefix function and KMP in code

Every program in this course reads its input through solve(std::istream&, std::ostream&). The playground has no keyboard input, so main feeds solve an embedded string; on a judge you call solve(std::cin, std::cout) and nothing else changes. The input here is a pattern and a text:

abab
abababcabab

main.cppc++23

#include <iostream>
#include <print>
#include <sstream>
#include <string>
#include <vector>

// pi[i] = length of the longest proper border of s[0..i]
std::vector<int> prefixFunction(const std::string& s) {
    std::vector<int> pi(s.size(), 0);
    for (std::size_t i = 1; i < s.size(); ++i) {
        int j = pi[i - 1];                            // best border of s[0..i-1]
        while (j > 0 && s[i] != s[j]) j = pi[j - 1];  // fall back to shorter borders
        if (s[i] == s[j]) ++j;
        pi[i] = j;
    }
    return pi;
}

// Start positions (0-based) of every occurrence of pat in text.
std::vector<int> kmpFind(const std::string& text, const std::string& pat) {
    std::vector<int> hits;
    if (pat.empty()) return hits;
    auto pi = prefixFunction(pat);
    int j = 0;  // how many characters of pat are matched right now
    for (int i = 0; i < int(text.size()); ++i) {
        while (j > 0 && text[i] != pat[j]) j = pi[j - 1];
        if (text[i] == pat[j]) ++j;
        if (j == int(pat.size())) {
            hits.push_back(i - j + 1);
            j = pi[j - 1];  // keep going: occurrences may overlap
        }
    }
    return hits;
}

void solve(std::istream& in, std::ostream& out) {
    std::string pat, text;
    in >> pat >> text;
    auto hits = kmpFind(text, pat);
    out << hits.size() << '\n';
    for (int p : hits) out << p << ' ';
    out << '\n';
}

int main() {
    for (int v : prefixFunction("abacaba")) std::print("{} ", v);
    std::println("");
    std::istringstream in("abab\nabababcabab\n");
    solve(in, std::cout);
}

Output

Press Run to compile and run this example.

0 0 1 0 1 2 3
3
0 2 7

The first line is the table above. The pattern abab occurs at positions 0, 2 and 7; the first two overlap, which is why a full match sets j = pi[j - 1] instead of starting from zero.

The prefix function needs O(m) time and memory for the pattern. The scan needs O(n) time and no extra memory beyond pi, so the whole search is O(n + m) in the worst case, with no assumptions about the input.

Why KMP is linear, counted

The inner while loop looks as if it could make KMP quadratic again. It cannot, and the argument is a small piece of amortized analysis. The value j goes up by at most one per text character, so over the whole scan it rises at most n times in total. Each step of the while loop lowers j by at least one, and j never goes below zero. So the total number of fallback steps over the whole scan is at most n, however they are distributed. The same argument bounds the work of prefixFunction by O(m).

Counting confirms it. This program runs KMP on the same worst-case input as the naive search and counts every character comparison, including those inside prefixFunction:

main.cppc++23

#include <print>
#include <string>
#include <vector>

long long comparisons = 0;

bool same(char a, char b) {
    ++comparisons;
    return a == b;
}

std::vector<int> prefixFunction(const std::string& s) {
    std::vector<int> pi(s.size(), 0);
    for (std::size_t i = 1; i < s.size(); ++i) {
        int j = pi[i - 1];
        while (j > 0 && !same(s[i], s[j])) j = pi[j - 1];
        if (same(s[i], s[j])) ++j;
        pi[i] = j;
    }
    return pi;
}

long long kmpCount(const std::string& text, const std::string& pat) {
    auto pi = prefixFunction(pat);
    long long hits = 0;
    int j = 0;
    for (char c : text) {
        while (j > 0 && !same(c, pat[j])) j = pi[j - 1];
        if (same(c, pat[j])) ++j;
        if (j == int(pat.size())) { ++hits; j = pi[j - 1]; }
    }
    return hits;
}

int main() {
    std::println("{:>6} {:>6} {:>12} {:>12}", "n", "m", "comparisons", "per char");
    for (int n : {2'000, 4'000, 8'000, 16'000}) {
        int m = n / 2;
        std::string text(n, 'a');
        std::string pat(m - 1, 'a');
        pat += 'b';
        comparisons = 0;
        kmpCount(text, pat);
        std::println("{:>6} {:>6} {:>12} {:>12.2f}", n, m, comparisons,
                     double(comparisons) / (n + m));
    }
}

Output

Press Run to compile and run this example.

     n      m  comparisons     per char
  2000   1000         7994         2.66
  4000   2000        15994         2.67
  8000   4000        31994         2.67
 16000   8000        63994         2.67

The naive search needed 64 million comparisons for the last row; KMP needs about 64 thousand. More important than the ratio is the last column: the comparisons per input character stay flat as n grows, which is what linear means. This implementation compares a character a second time after the while loop exits on a match, so its constant is at most 3 per character rather than the textbook 2; the shape is the same.

Stress testing KMP against `std::string::find`

KMP is short, and short code with indices is where off-by-one mistakes hide. The habit from Fast I/O, Contest Templates and Stress Testing applies: compare against an obviously correct reference on thousands of small random inputs. Here the reference is std::string::find called from every position, and the inputs use only the letters a and b, because a tiny alphabet produces many overlapping and almost-matching cases. The sizes grow with the test number, so the first failure found is a small one.

The program runs the harness twice: once on a version with a realistic bug (after a full match, it resets j to 0 instead of to pi[j - 1]), and once on the correct version.

main.cppc++23

#include <cstdint>
#include <print>
#include <string>
#include <vector>

struct Lcg {
    std::uint64_t s;
    std::uint32_t next() {
        s = s * 6364136223846793005ULL + 1442695040888963407ULL;
        return std::uint32_t(s >> 33);
    }
    int range(int lo, int hi) { return lo + int(next() % std::uint32_t(hi - lo + 1)); }
};

std::vector<int> prefixFunction(const std::string& s) {
    std::vector<int> pi(s.size(), 0);
    for (std::size_t i = 1; i < s.size(); ++i) {
        int j = pi[i - 1];
        while (j > 0 && s[i] != s[j]) j = pi[j - 1];
        if (s[i] == s[j]) ++j;
        pi[i] = j;
    }
    return pi;
}

std::vector<int> kmpFind(const std::string& text, const std::string& pat, bool buggy) {
    std::vector<int> hits;
    auto pi = prefixFunction(pat);
    int j = 0;
    for (int i = 0; i < int(text.size()); ++i) {
        while (j > 0 && text[i] != pat[j]) j = pi[j - 1];
        if (text[i] == pat[j]) ++j;
        if (j == int(pat.size())) {
            hits.push_back(i - j + 1);
            j = buggy ? 0 : pi[j - 1];  // the bug: forget the border after a match
        }
    }
    return hits;
}

// The obviously correct reference: std::string::find from every position.
std::vector<int> findAll(const std::string& text, const std::string& pat) {
    std::vector<int> hits;
    for (auto p = text.find(pat); p != std::string::npos; p = text.find(pat, p + 1))
        hits.push_back(int(p));
    return hits;
}

std::string randomString(Lcg& rng, int len) {
    std::string s;
    for (int i = 0; i < len; ++i) s += char('a' + rng.range(0, 1));  // tiny alphabet
    return s;
}

void stress(bool buggy) {
    Lcg rng{2024};
    for (int t = 0; t < 5000; ++t) {
        int maxLen = 1 + t / 500;  // small cases first: the first failure is small
        std::string text = randomString(rng, rng.range(0, maxLen + 3));
        std::string pat = randomString(rng, rng.range(1, maxLen));
        if (kmpFind(text, pat, buggy) != findAll(text, pat)) {
            std::println("{}: mismatch on text=\"{}\" pattern=\"{}\" "
                         "(kmp {} hits, reference {})", buggy ? "buggy" : "fixed",
                         text, pat, kmpFind(text, pat, buggy).size(),
                         findAll(text, pat).size());
            return;
        }
    }
    std::println("{}: 5000 random cases, all agree", buggy ? "buggy" : "fixed");
}

int main() {
    stress(true);
    stress(false);
}

Output

Press Run to compile and run this example.

buggy: mismatch on text="abaaa" pattern="aa" (kmp 1 hits, reference 2)
fixed: 5000 random cases, all agree

The counterexample is five characters long and explains itself: aa occurs in abaaa at positions 2 and 3, and the two occurrences share a character. The buggy version forgets that shared character after the first match. The sample in the previous section happens to contain overlapping occurrences, so it would expose this bug too; hand-written samples often do not.

Notice that the random texts include the empty string (rng.range(0, ...)). Empty input, a pattern longer than the text and a pattern equal to the text are all covered without anyone having to think of them.

Periods from the prefix function

Borders and periods are two views of the same thing. An integer p is a period of s if s[i] == s[i + p] for every i where both sides exist. If s has a border of length b, then p = n - b is a period (shift the string by p and the border lines up with itself), and the reverse holds as well. So the longest border gives the shortest period: n - pi[n - 1].

A second, stricter question asks for the shortest block that, repeated a whole number of times, produces s. The shortest period answers it when it divides n. When it does not, no block shorter than s works at all; this follows from the Fine and Wilf periodicity lemma, and the program below checks it exhaustively rather than asking you to take it on trust.

An original problem to try it on. A tiling machine prints a strip of colored tiles, one letter per tile, by repeating a stencil. For each strip, report the shortest stencil length if the last copy may be cut off, and the shortest stencil that tiles the strip exactly. Input: the number of strips, then one strip per line.

4
abcabcabc
abcabcab
abaab
zzzzzz

main.cppc++23

#include <iostream>
#include <print>
#include <sstream>
#include <string>
#include <vector>

std::vector<int> prefixFunction(const std::string& s) {
    std::vector<int> pi(s.size(), 0);
    for (std::size_t i = 1; i < s.size(); ++i) {
        int j = pi[i - 1];
        while (j > 0 && s[i] != s[j]) j = pi[j - 1];
        if (s[i] == s[j]) ++j;
        pi[i] = j;
    }
    return pi;
}

// Shortest p with s[i] == s[i + p] for all valid i (the last copy may be cut off).
int shortestPeriod(const std::string& s) {
    return int(s.size()) - prefixFunction(s).back();
}

// Shortest block that, repeated a whole number of times, gives s.
int shortestTile(const std::string& s) {
    int n = int(s.size()), p = shortestPeriod(s);
    return n % p == 0 ? p : n;
}

// Brute force: try every p; wholeOnly asks for p to divide the length.
int brute(const std::string& s, bool wholeOnly) {
    int n = int(s.size());
    for (int p = 1; p < n; ++p) {
        if (wholeOnly && n % p != 0) continue;
        bool ok = true;
        for (int i = p; i < n && ok; ++i) ok = s[i] == s[i - p];
        if (ok) return p;
    }
    return n;
}

void solve(std::istream& in, std::ostream& out) {
    int q;
    in >> q;
    while (q--) {
        std::string s;
        in >> s;
        out << s << ": period " << shortestPeriod(s) << ", tile "
            << shortestTile(s) << '\n';
    }
}

int main() {
    std::istringstream in("4\nabcabcabc\nabcabcab\nabaab\nzzzzzz\n");
    solve(in, std::cout);

    // Exhaustive check: every string over {a, b} of length 1 to 14.
    long long checked = 0, wrong = 0;
    for (int n = 1; n <= 14; ++n)
        for (int mask = 0; mask < (1 << n); ++mask) {
            std::string s;
            for (int i = 0; i < n; ++i) s += ((mask >> i) & 1) ? 'b' : 'a';
            ++checked;
            wrong += shortestPeriod(s) != brute(s, false);
            wrong += shortestTile(s) != brute(s, true);
        }
    std::println("checked {} strings against brute force, {} wrong", checked, wrong);
}

Output

Press Run to compile and run this example.

abcabcabc: period 3, tile 3
abcabcab: period 3, tile 8
abaab: period 3, tile 5
zzzzzz: period 1, tile 1
checked 32766 strings against brute force, 0 wrong

abcabcab has period 3 (the stencil abc with the last copy cut short) but no exact tiling shorter than itself, because 3 does not divide 8. When the inputs are small enough to enumerate, an exhaustive check is stronger than a random one: here every binary string up to length 14 was tested, not a sample of them.

The Z-function: matching against the start of the string

The Z-function of s is the array z where z[i] is the length of the longest common prefix of s and the suffix s[i..]. The value z[0] is not meaningful; this lesson sets it to 0. For s = aabxaab:

z[1] = 1: the suffix abxaab shares only a with s.
z[4] = 3: the suffix aab matches the first three characters.
z[5] = 1: the suffix ab shares only a.
Positions 2, 3 and 6 start with b or x, so their values are 0.

Computing each value by direct comparison is O(n^2) on strings like aaaa.... The linear algorithm keeps the window [l, r): the match found so far that reaches furthest to the right, so s[l..r) equals s[0..r-l). For a position i inside the window, the character at i corresponds to position i - l near the start of the string, whose value z[i - l] is already known. That gives a free lower bound, capped by the window's end; direct comparison continues only beyond r, and every successful comparison there moves r to the right. Since r never moves left and never passes n, the total work is O(n).

The prefix function and the Z-function hold the same information in different shapes. A box of z[i] matching characters starting at i says that, for every k below z[i], the prefix s[0..i+k] has a border of length k + 1. The first box to cover a position gives its longest border. The program converts z into pi this way and checks both arrays against slower definitions on every binary string up to length 12:

main.cppc++23

#include <algorithm>
#include <print>
#include <string>
#include <vector>

// z[i] = length of the longest common prefix of s and s[i..]; z[0] is left 0.
std::vector<int> zFunction(const std::string& s) {
    int n = int(s.size());
    std::vector<int> z(n, 0);
    int l = 0, r = 0;  // [l, r) is the rightmost window known to match a prefix
    for (int i = 1; i < n; ++i) {
        if (i < r) z[i] = std::min(r - i, z[i - l]);  // reuse what the window says
        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;
}

std::vector<int> zNaive(const std::string& s) {
    int n = int(s.size());
    std::vector<int> z(n, 0);
    for (int i = 1; i < n; ++i)
        while (i + z[i] < n && s[z[i]] == s[i + z[i]]) ++z[i];
    return z;
}

std::vector<int> prefixFunction(const std::string& s) {
    std::vector<int> pi(s.size(), 0);
    for (std::size_t i = 1; i < s.size(); ++i) {
        int j = pi[i - 1];
        while (j > 0 && s[i] != s[j]) j = pi[j - 1];
        if (s[i] == s[j]) ++j;
        pi[i] = j;
    }
    return pi;
}

// The z-box at i gives s[0..i+k] a border of length k + 1 for every k < z[i].
// The first (leftmost) box covering a position gives the longest one.
std::vector<int> piFromZ(const std::vector<int>& z) {
    int n = int(z.size());
    std::vector<int> pi(n, 0);
    for (int i = 1; i < n; ++i)
        for (int k = z[i] - 1; k >= 0 && pi[i + k] == 0; --k) pi[i + k] = k + 1;
    return pi;
}

int main() {
    for (int v : zFunction("aabxaab")) std::print("{} ", v);
    std::println("");

    long long checked = 0, wrong = 0;
    for (int n = 1; n <= 12; ++n)
        for (int mask = 0; mask < (1 << n); ++mask) {
            std::string s;
            for (int i = 0; i < n; ++i) s += ((mask >> i) & 1) ? 'b' : 'a';
            auto z = zFunction(s);
            ++checked;
            wrong += z != zNaive(s);
            wrong += piFromZ(z) != prefixFunction(s);
        }
    std::println("checked {} strings: {} disagreements", checked, wrong);
}

Output

Press Run to compile and run this example.

0 1 0 0 3 1 0
checked 8190 strings: 0 disagreements

The inner loop of piFromZ stops as soon as it reaches a position that is already set, so each position is written once and the conversion is O(n). Which one should you use? Pattern matching works with either. The prefix function streams: it can process a text one character at a time without storing it. The Z-function is often easier to reason about when the question is "how much of the start of the string reappears at position i", for example when comparing every suffix of a string with its beginning.

Prefix Sums, Fenwick Trees and Segment Trees

Number Theory and Bit Tricks