String Algorithms Complete Guide — KMP, Z, Rolling Hash, Suffix Array, Manacher

Problem Statement

This is the master guide for the entire String Algorithms category (problems 01 through 19). The goal is to give you the mental model and templates for every advanced string technique, so that any pattern-matching, hashing, or suffix question reduces to "pick the algorithm and adapt the template".

Constraints:

Cover six core algorithm families
Provide Python and JavaScript templates that compile as-is
Include a complexity comparison table
Map each algorithm to canonical LeetCode problems

Input:  Any advanced string problem
Output: Algorithm name + template + Big-O analysis

Why This Problem Matters

Naive string matching is O(nm). Real-world tools — grep, ripgrep, the regex engines inside V8 and CPython, the suffix-array indexes inside Elasticsearch — all use these algorithms because the difference between O(nm) and O(n+m) is the difference between a tool that finishes in milliseconds and one that hangs for minutes.

Google asks KMP because it tests whether you understand that information from failed comparisons is not lost. Meta asks rolling hash because it shows up in every duplicate-detection and similarity problem. Amazon asks Manacher because palindrome problems are a favorite onsite filter. Every algorithm in this guide has been asked at FAANG within the past two years.

This page consolidates the entire family. Read it once to build the map. Then drill the templates until they are reflex.

The Core Insight

There are exactly six string-algorithm families, and they answer six distinct questions:

"Does pattern P appear in text T?" — KMP, Z, Rabin-Karp
"How many times does P appear in T?" — same three, plus Aho-Corasick for many patterns
"What is the longest palindrome in T?" — Manacher
"What is the longest common substring of A and B?" — suffix array or DP
"How many distinct substrings does T have?" — suffix array with LCP
"Are these two substrings of T equal?" — polynomial hashing

Pick the right family from the question, plug in the template, ship.

Visual Dry Run

Algorithm	Preprocess	Search	Space	Best For
Naive	O(1)	O(n*m)	O(1)	Tiny inputs
KMP	O(m)	O(n)	O(m)	Single-pattern exact match
Z-algorithm	O(n+m)	included	O(n+m)	All prefix matches
Rabin-Karp	O(m)	O(n+m) avg	O(1)	Multi-pattern, plagiarism
Suffix array	O(n log n)	O(m log n)	O(n)	Many queries on fixed text
Manacher	O(n)	included	O(n)	Longest palindrome
Aho-Corasick	O(sum m)	O(n + z)	O(sum m)	Many patterns at once

Solution (Optimal)

Family 1 — KMP Failure Function

def kmp_lps(pattern):
    m = len(pattern)
    lps = [0] * m
    k = 0
    for i in range(1, m):
        while k > 0 and pattern[k] != pattern[i]:
            k = lps[k - 1]
        if pattern[k] == pattern[i]:
            k += 1
        lps[i] = k
    return lps
 
def kmp_search(text, pattern):
    if not pattern:
        return 0
    lps = kmp_lps(pattern)
    j = 0
    for i, ch in enumerate(text):
        while j > 0 and pattern[j] != ch:
            j = lps[j - 1]
        if pattern[j] == ch:
            j += 1
        if j == len(pattern):
            return i - j + 1
    return -1

var kmpSearch = function(text, pattern) {
    if (!pattern.length) return 0;
    const m = pattern.length;
    const lps = new Array(m).fill(0);
    let k = 0;
    for (let i = 1; i < m; i++) {
        while (k > 0 && pattern[k] !== pattern[i]) k = lps[k - 1];
        if (pattern[k] === pattern[i]) k++;
        lps[i] = k;
    }
    let j = 0;
    for (let i = 0; i < text.length; i++) {
        while (j > 0 && pattern[j] !== text[i]) j = lps[j - 1];
        if (pattern[j] === text[i]) j++;
        if (j === m) return i - j + 1;
    }
    return -1;
};

Time: O(n + m) Space: O(m)

Family 2 — Z-Algorithm

def z_function(s):
    n = len(s)
    z = [0] * n
    l = r = 0
    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

var zFunction = function(s) {
    const n = s.length;
    const z = new Array(n).fill(0);
    let l = 0, r = 0;
    for (let i = 1; i < n; i++) {
        if (i < r) z[i] = Math.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;
};

Time: O(n) Space: O(n)

Family 3 — Rabin-Karp Rolling Hash

def rabin_karp(text, pattern, base=257, mod=10**9 + 7):
    n, m = len(text), len(pattern)
    if m > n:
        return -1
    pow_m = pow(base, m - 1, mod)
    p_hash = 0
    t_hash = 0
    for i in range(m):
        p_hash = (p_hash * base + ord(pattern[i])) % mod
        t_hash = (t_hash * base + ord(text[i])) % mod
    for i in range(n - m + 1):
        if p_hash == t_hash and text[i:i + m] == pattern:
            return i
        if i + m < n:
            t_hash = ((t_hash - ord(text[i]) * pow_m) * base + ord(text[i + m])) % mod
    return -1

var rabinKarp = function(text, pattern) {
    const n = text.length, m = pattern.length;
    if (m > n) return -1;
    const base = 257n, mod = 1000000007n;
    let powM = 1n;
    for (let i = 0; i < m - 1; i++) powM = (powM * base) % mod;
    let pHash = 0n, tHash = 0n;
    for (let i = 0; i < m; i++) {
        pHash = (pHash * base + BigInt(pattern.charCodeAt(i))) % mod;
        tHash = (tHash * base + BigInt(text.charCodeAt(i))) % mod;
    }
    for (let i = 0; i <= n - m; i++) {
        if (pHash === tHash && text.slice(i, i + m) === pattern) return i;
        if (i + m < n) {
            tHash = ((tHash - BigInt(text.charCodeAt(i)) * powM) * base + BigInt(text.charCodeAt(i + m))) % mod;
            tHash = (tHash + mod) % mod;
        }
    }
    return -1;
};

Time: O(n + m) average Space: O(1)

Family 4 — Manacher (Longest Palindrome)

def manacher(s):
    t = '#' + '#'.join(s) + '#'
    n = len(t)
    p = [0] * n
    c = r = 0
    for i in range(n):
        mirror = 2 * c - i
        if i < r:
            p[i] = min(r - i, p[mirror])
        while i + p[i] + 1 < n and i - p[i] - 1 >= 0 and t[i + p[i] + 1] == t[i - p[i] - 1]:
            p[i] += 1
        if i + p[i] > r:
            c, r = i, i + p[i]
    max_len = max(p)
    center = p.index(max_len)
    start = (center - max_len) // 2
    return s[start:start + max_len]

var manacher = function(s) {
    const t = '#' + s.split('').join('#') + '#';
    const n = t.length;
    const p = new Array(n).fill(0);
    let c = 0, r = 0;
    for (let i = 0; i < n; i++) {
        const mirror = 2 * c - i;
        if (i < r) p[i] = Math.min(r - i, p[mirror]);
        while (i + p[i] + 1 < n && i - p[i] - 1 >= 0 && t[i + p[i] + 1] === t[i - p[i] - 1]) p[i]++;
        if (i + p[i] > r) { c = i; r = i + p[i]; }
    }
    let maxLen = 0, center = 0;
    for (let i = 0; i < n; i++) if (p[i] > maxLen) { maxLen = p[i]; center = i; }
    const start = Math.floor((center - maxLen) / 2);
    return s.slice(start, start + maxLen);
};

Time: O(n) Space: O(n)

Common Mistakes

Off-by-one in KMP failure function — confusion between "length of LPS up to i" and "index of LPS".
Hash collisions in Rabin-Karp — always verify on equal hash before claiming a match.
Using a single hash with a small modulus — collision probability becomes practical. Use double hashing for adversarial inputs.
Manacher without sentinel insertion — fails to handle even-length palindromes.
Suffix array DP recurrence off by one — treat empty prefix as rank zero.

Interview Tips

For "find pattern in text", default to KMP unless the interviewer says "many patterns" (then Aho-Corasick or rolling hash).
For "longest palindromic substring", expand-around-center is acceptable in O(n^2). Manacher only if the interviewer asks for linear.
Always state hash-collision verification when using rolling hash.
For substring queries on a fixed text, mention suffix arrays even if you don't implement them — interviewers care about the trade-off awareness.

Follow-up Questions

"Can KMP find all occurrences?" — Yes, on match, jump j to lps[j-1] and continue.
"What is the LPS of aabaabaaa?" — Compute step by step: 0,1,0,1,2,3,4,5,2.
"Why use two moduli for rolling hash?" — To make collisions astronomically unlikely under adversarial inputs.
"Can suffix array be built in O(n)?" — Yes, with the SA-IS algorithm. O(n log n) is what most interviewers expect.
"How does Aho-Corasick differ from KMP?" — KMP is one pattern; Aho-Corasick is a trie of patterns with failure links.

Key Takeaways

Six algorithm families cover every advanced string question — KMP, Z, Rabin-Karp, suffix array, Manacher, Aho-Corasick.
KMP and Z both run in O(n + m) for single-pattern search and reuse the same intuition (longest border).
Rabin-Karp wins when you need many patterns or sliding-window similarity.
Manacher is the only true linear-time longest-palindrome algorithm.
Suffix arrays answer many substring queries on a fixed text in logarithmic time per query.
Aho-Corasick is KMP generalized to a trie — use it when the pattern set is large and fixed.
Memorize the templates first, then practice mapping problems to families.

Problem Statement#

Why This Problem Matters#

The Core Insight#

Visual Dry Run#

Solution (Optimal)#

Family 1 — KMP Failure Function#

Family 2 — Z-Algorithm#

Family 3 — Rabin-Karp Rolling Hash#

Family 4 — Manacher (Longest Palindrome)#

Common Mistakes#

Interview Tips#

Follow-up Questions#

Key Takeaways#

Related reading