String algorithms: KMP, Z and hashing

Searching for a pattern of length m in a text of length n looks like a solved problem — text.find(pattern) — and usually it is. But the obvious algorithm has a nasty worst case, and the ideas that fix it (borders, the prefix function, the Z-function, rolling hashes) solve a whole family of string problems: all occurrences, periods, repeated substrings, palindromes, plagiarism checks. The common theme: never re-read text you have already matched.

1. Naive search and its worst case

Try every alignment, compare left to right, stop at the first mismatch:

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

// Counts character comparisons of the naive search for all occurrences.
std::size_t naive_comparisons(std::string_view text, std::string_view pat) {
    std::size_t cmp = 0;
    for (std::size_t i = 0; i + pat.size() <= text.size(); ++i) {
        std::size_t j = 0;
        while (j < pat.size()) {
            ++cmp;
            if (text[i + j] != pat[j]) break;
            ++j;
        }
    }
    return cmp;
}

int main() {
    std::string text(2000, 'a');
    std::string random_pat = "xyz";
    std::string evil_pat = std::string(999, 'a') + "b";
    std::println("random pattern: {} comparisons", naive_comparisons(text, random_pat));
    std::println("aaa...ab:       {} comparisons", naive_comparisons(text, evil_pat));
}

On ordinary text, mismatches come early and naive search is fast. On aaaa…a searching for aaa…ab, every alignment matches m − 1 characters before failing: (n − m + 1) · m comparisons, about a million above. With n = 10⁶ and m = 5·10⁵ that's 2.5·10¹¹ — minutes, not milliseconds. And the waste is obvious: after matching aaaa…a at position i, we know the next m − 2 characters of the text, yet we read them again.

2. Borders and the prefix function

A border of a string is a proper prefix that is also a suffix: "abacaba" has borders "a" and "aba" (not the whole string — proper).

The prefix function π[i] is the length of the longest border of the prefix s[0..i] (inclusive):

π[6] = 3 because "aba" is both a prefix and a suffix of "abacaba".

Why it helps: if we have matched s[0..i] and the next character mismatches, the longest shorter prefix that is still matched ending here is exactly the longest border, π[i]. We can continue from there without moving backwards in the text.

Computing π in O(n)

Two facts:

1. π[i] ≤ π[i−1] + 1 — a border can grow by at most one character per step.
2. If extending the border of length k = π[i−1] fails (s[i] ≠ s[k]), the next candidate is the longest border of that border: k = π[k−1].

#include <cstddef>
#include <print>
#include <string_view>
#include <vector>

std::vector<std::size_t> prefix_function(std::string_view s) {
    std::vector<std::size_t> pi(s.size(), 0);
    for (std::size_t i = 1; i < s.size(); ++i) {
        std::size_t k = pi[i - 1];              // longest border of s[0..i-1]
        while (k > 0 && s[i] != s[k]) k = pi[k - 1];   // fall back to a shorter border
        if (s[i] == s[k]) ++k;                  // extend it by s[i]
        pi[i] = k;
    }
    return pi;
}

int main() {
    for (auto x : prefix_function("abacaba")) std::print("{} ", x);
    std::println("");
}

Invariant: at the top of iteration i, k is the length of a border of s[0..i−1], and every longer border has already been ruled out. Cost: k increases by at most 1 per iteration and every fallback decreases it, so the total number of fallbacks is at most n: O(n) overall.

The classic slip is k = π[k] instead of k = π[k − 1]: π[k] describes the prefix of length k + 1, which isn't matched.

3. KMP: searching with the prefix function

Knuth–Morris–Pratt runs the same loop with the pattern on one side and the text on the other. j is "how many pattern characters are currently matched":

std::size_t j = 0;
for (std::size_t i = 0; i < text.size(); ++i) {
    while (j > 0 && text[i] != pat[j]) j = pi[j - 1];
    if (text[i] == pat[j]) ++j;
    if (j == pat.size()) {             // full match ending at i
        out.push_back(i + 1 - pat.size());
        j = pi[j - 1];                  // keep the border: overlapping matches
    }
}

i only moves forward, so search is O(n + m) including building π. Note the line after a full match: resetting j = 0 would skip overlapping matches — "aa" occurs in "aaaa" at 0, 1 and 2.

An equivalent trick: compute the prefix function of pattern + '#' + text where # occurs in neither; every position where π equals m is a match. It needs a separator character that can't appear — awkward for arbitrary bytes — so the streaming loop above is the general tool.

4. The Z-function

The Z-function is the other classic: z[i] is the length of the longest common prefix of s and the suffix s[i..]. By convention here z[0] = n.

It is computed in O(n) by remembering the rightmost match window [l, r) (a substring that equals a prefix): inside the window, z[i] is at least min(r − i, z[i − l]) — we copy what we already know — and only characters beyond r are compared.

Faded example: Z-based search

Fill in the blanks: use the Z-function of the pattern plus a direct scan of the text, without a separator character. (Hint: compute, for every text position, the longest common prefix with the pattern, reusing a window like the Z-function does.)

// lcp[i] = longest common prefix of pattern and text[i..]
std::size_t l = 0, r = 0;           // text window [l, r) equals pattern[0 .. r-l)
for (std::size_t i = 0; i < text.size(); ++i) {
    std::size_t len = (i < r) ? std::min(r - i, /* ??? */) : 0;
    while (len < pat.size() && i + len < text.size() && text[i + len] == pat[len]) ++len;
    if (i + len > r) { l = i; r = i + len; }
    if (len == pat.size()) out.push_back(i);
}

5. Periods

A string s has period p if s[i] == s[i + p] for every valid i ("abcabca" has period 3). Periods and borders are two views of the same thing: s has a border of length b exactly when it has period n − b. So the smallest period is n − π[n − 1] — the longest border gives the shortest period.

Careful with the empty string: π[n − 1] with n = 0 indexes position SIZE_MAX. Handle n == 0 first.

6. Rolling hashes (Rabin–Karp)

A different idea: turn every length-k window into a number and compare numbers. The polynomial hash

h(s) = s[0]·B^(k−1) + s[1]·B^(k−2) + … + s[k−1]      (mod M)

can be rolled: drop the first character and append the next in O(1), h' = (h − s[i]·B^(k−1))·B + s[i+k]. That gives every window's hash in O(n) total — great for "how many distinct substrings of length k", "longest repeated substring" (with binary search on k), or matching many patterns.

Collisions are real

Different strings can have the same hash. Two common choices:

• M = 2⁶⁴ (just let std::uint64_t wrap — well-defined for unsigned types): fast, but there is a famous adversarial input. For the Thue–Morse string (t[i] = parity of the number of 1 bits in i), the halves of a length-2¹² block collide for every base. No choice of base saves you.
• A large prime M (e.g. 2⁶¹ − 1) with a random base: collisions become unlikely per comparison (≈ k/M), but over millions of comparisons they still happen, and a fixed base can be attacked.

#include <bit>
#include <cstddef>
#include <cstdint>
#include <print>
#include <string>
#include <string_view>

std::uint64_t poly_hash(std::string_view s, std::uint64_t base) {
    std::uint64_t h = 0;
    for (unsigned char c : s) h = h * base + c;    // wraps mod 2^64
    return h;
}

int main() {
    std::string t(4096, 'a');
    for (std::size_t i = 0; i < t.size(); ++i)
        if (std::popcount(i) & 1) t[i] = 'b';
    std::string_view left(t.data(), 2048), right(t.data() + 2048, 2048);
    std::println("equal strings? {}", left == right);
    for (std::uint64_t base : {31u, 131u, 1000003u})
        std::println("base {:7}: same hash? {}", base, poly_hash(left, base) == poly_hash(right, base));
}

So: a hash match is a hint, not a proof. Either verify every match by comparing the actual characters (always correct; costs O(k) per true match), or use two independent hashes and accept a tiny, quantified risk — and say so. Double hashing (two moduli or two bases) makes accidental collisions astronomically unlikely, but only verification makes them impossible.

7. When to just use the library

• std::string_view::find — fine for one-off searches; implementations use a fast memchr-based scan and are hard to beat on ordinary text, but give no worst-case guarantee.
• std::search(first, last, std::boyer_moore_searcher(pb, pe)) (C++17, <functional>) — Boyer–Moore skips ahead using the pattern's last characters; excellent for long patterns over large alphabets. It needs random-access iterators (it does arithmetic on them), so it won't compile over a std::list<char>. std::boyer_moore_horspool_searcher is the lighter variant; std::default_searcher is the naive one.
• Write KMP/Z yourself when you need all occurrences with a guaranteed O(n + m), streaming input, the π/Z arrays themselves (periods, borders), or many queries against one preprocessed pattern.

8. A byte-alphabet pitfall: char is often signed

On x86-64 Linux, char is signed. A byte like 0xE9 (é in Latin-1, or part of a UTF-8 sequence) is the value −23 as a char. Using it as an index — count[c] for a 256-entry table — reads memory before the array:

int count[256] = {};
for (char c : text) ++count[c];                           // UB for bytes >= 0x80
for (char c : text) ++count[static_cast<unsigned char>(c)]; // correct

The same applies to <cctype> functions (std::isalpha(c) with a negative c other than EOF is UB) and to hash mixing where you want a value in 0–255. Convert through unsigned char at the boundary.

Summary

• Naive search is O(n·m) in the worst case (aaaa…ab); fine on ordinary text.
• The prefix function π[i] = longest border of s[0..i]; computed in O(n) with the fallback k = π[k − 1]. KMP uses it to search in O(n + m) and keeps overlapping matches by continuing from π[m − 1].
• The Z-function gives longest common prefixes with the whole string, using a reusable window [l, r).
• Smallest period = n − π[n − 1] (guard n == 0).
• Rolling hashes compare windows in O(1), but collisions exist — Thue–Morse breaks every mod-2⁶⁴ polynomial hash. Verify matches, or use double hashing and know the risk.
• Prefer std::string_view::find / std::boyer_moore_searcher for everyday searching; index tables with unsigned char.