String Algorithms

Why special algorithms?

Naive substring search compares the pattern at every position: O(n·m). For n, m up to 10⁵ that's 10¹⁰ — too slow. These algorithms preprocess the pattern (or text) to never re-examine characters unnecessarily, giving O(n + m).

KMP: the prefix function

pi[i] = length of the longest proper prefix of s[0..i] that is also a suffix of it.

s  = a b a b a c a
pi = 0 0 1 2 3 0 1

When a mismatch happens, instead of restarting, KMP jumps to the longest border that could still match.

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

def kmp_search(text, pattern):
    """All start indices of pattern in text."""
    pi = prefix_function(pattern)
    res, k = [], 0
    for i, ch in enumerate(text):
        while k > 0 and ch != pattern[k]:
            k = pi[k - 1]
        if ch == pattern[k]:
            k += 1
        if k == len(pattern):
            res.append(i - k + 1)
            k = pi[k - 1]
    return res

vector<int> prefixFunction(const string& s) {
    vector<int> pi(s.size(), 0);
    for (int i = 1; i < (int)s.size(); i++) {
        int k = pi[i - 1];
        while (k > 0 && s[i] != s[k]) k = pi[k - 1];
        if (s[i] == s[k]) k++;
        pi[i] = k;
    }
    return pi;
}
vector<int> kmpSearch(const string& text, const string& pat) {
    vector<int> pi = prefixFunction(pat), res;
    int k = 0;
    for (int i = 0; i < (int)text.size(); i++) {
        while (k > 0 && text[i] != pat[k]) k = pi[k - 1];
        if (text[i] == pat[k]) k++;
        if (k == (int)pat.size()) { res.push_back(i - k + 1); k = pi[k - 1]; }
    }
    return res;
}

Why it's O(n): k increases by at most 1 per character and every fallback decreases it, so the total number of fallbacks is ≤ n.

Uses of the prefix function

Z-function

z[i] = length of the longest substring starting at i that matches a prefix of s. (z[0] is usually set to 0 or n.)

def z_function(s):
    n = len(s)
    z = [0] * n
    l = r = 0                          # [l, r) is the rightmost match window found
    for i in range(1, n):
        if i < r:
            z[i] = min(r - i, z[i - l])
        while i + z[i] < n and s[z[i]] == s[i + z[i]]:
            z[i] += 1
        if i + z[i] > r:
            l, r = i, i + z[i]
    return z

vector<int> zFunction(const string& s) {
    int n = 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]);
        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;
}

Pattern search: compute z of pattern + "#" + text; matches are where z[i] == len(pattern). Z and KMP solve mostly the same problems — pick the one you can write from memory.

Rolling hash (Rabin-Karp)

Treat a string as a number in base B modulo a large prime M. The hash of any substring can be computed in O(1) from prefix hashes, so substring equality becomes an O(1) comparison (with a tiny collision probability).

class RollingHash:
    def __init__(self, s, base=911382323, mod=(1 << 61) - 1):
        self.mod = mod
        n = len(s)
        self.h = [0] * (n + 1)
        self.p = [1] * (n + 1)
        for i, ch in enumerate(s):
            self.h[i + 1] = (self.h[i] * base + ord(ch)) % mod
            self.p[i + 1] = (self.p[i] * base) % mod

    def get(self, l, r):               # hash of s[l:r]
        return (self.h[r] - self.h[l] * self.p[r - l]) % self.mod

struct RollingHash {
    static const unsigned long long MOD = (1ULL << 61) - 1;
    vector<unsigned long long> h, p;
    static unsigned long long mul(unsigned long long a, unsigned long long b) {
        __uint128_t c = (__uint128_t)a * b;
        unsigned long long lo = (unsigned long long)(c & MOD), hi = (unsigned long long)(c >> 61);
        unsigned long long r = lo + hi;
        return r >= MOD ? r - MOD : r;
    }
    RollingHash(const string& s, unsigned long long base = 911382323) : h(s.size() + 1, 0), p(s.size() + 1, 1) {
        for (size_t i = 0; i < s.size(); i++) {
            h[i + 1] = (mul(h[i], base) + (unsigned char)s[i]) % MOD;
            p[i + 1] = mul(p[i], base);
        }
    }
    unsigned long long get(int l, int r) {        // hash of s[l, r)
        return (h[r] + MOD - mul(h[l], p[r - l])) % MOD;
    }
};

Binary search + hashing

“Longest substring that appears twice” is monotone in length (if length L repeats, so does L − 1). Binary search L and check with a set of window hashes: O(n log n).

def longest_dup_substring(s):
    rh = RollingHash(s)
    def find(L):
        seen = {}
        for i in range(len(s) - L + 1):
            h = rh.get(i, i + L)
            if h in seen:
                return i
            seen[h] = i
        return -1
    lo, hi, start = 1, len(s) - 1, -1
    while lo <= hi:
        mid = (lo + hi) // 2
        idx = find(mid)
        if idx != -1:
            start, best = idx, mid
            lo = mid + 1
        else:
            hi = mid - 1
    return "" if start == -1 else s[start:start + best]

Manacher's algorithm (all palindromes in O(n))

Transform s into #a#b#a# so every palindrome has odd length, then compute p[i] = radius of the longest palindrome centered at i, reusing the mirror position inside the rightmost known palindrome.

def manacher(s):
    t = "#" + "#".join(s) + "#"
    n = len(t)
    p = [0] * n
    center = right = 0
    for i in range(n):
        if i < right:
            p[i] = min(right - i, p[2 * center - i])
        while i - p[i] - 1 >= 0 and i + p[i] + 1 < n and t[i - p[i] - 1] == t[i + p[i] + 1]:
            p[i] += 1
        if i + p[i] > right:
            center, right = i, i + p[i]
    best = max(range(n), key=p.__getitem__)
    start = (best - p[best]) // 2
    return s[start:start + p[best]]     # longest palindromic substring

p[i] in the transformed string equals the palindrome's length in the original. Summing (p[i] + 1) // 2 over all i counts all palindromic substrings.

Suffix structures (awareness)

These rarely appear in interviews but are standard in competitive programming. Aho-Corasick is “KMP on a trie”.

Picking a tool

Common mistakes

• KMP fallback using pi[k] instead of pi[k − 1].
• Separator character that appears in the input when concatenating.
• Negative values from modular subtraction in hashing (add mod before % in C++).
• Trusting a single small-modulus hash on adversarial tests.