String Algorithms

"String fundamentals: reverse, rotation, comparison, pattern matching basics, anagram detection."

Deep Dive Tutorial

String algorithms solve the "find pattern P in text T" problem faster than the naive O(n×m). The key insight in KMP: when a mismatch happens, the prefix already matched tells us how far we can skip. The key insight in Z-algorithm: Z[i] = length of longest match starting at i and the start of the string. Both run in O(n+m).

KMP — Knuth-Morris-Pratt

key

LPS array (Longest Proper Prefix that is also a Suffix): lps[i] = length of longest prefix of pattern[0..i] that is also a suffix.

KMP uses lps to avoid re-examining characters after a mismatch. When mismatch at pattern[j] and text[i], we jump j back to lps[j-1] instead of starting over.

Build LPS array + KMP search

function buildLPS(pattern) {
    const lps = new Array(pattern.length).fill(0);
    let len = 0, i = 1;
    while (i < pattern.length) {
        if (pattern[i] === pattern[len]) {
            lps[i++] = ++len;
        } else if (len > 0) {
            len = lps[len - 1];   // fall back using LPS (don't increment i)
        } else {
            lps[i++] = 0;
        }
    }
    return lps;
}

function kmpSearch(text, pattern) {
    const lps = buildLPS(pattern);
    const matches = [];
    let i = 0, j = 0;
    while (i < text.length) {
        if (text[i] === pattern[j]) { i++; j++; }
        if (j === pattern.length) {
            matches.push(i - j);   // found at index i-j
            j = lps[j - 1];
        } else if (i < text.length && text[i] !== pattern[j]) {
            j > 0 ? j = lps[j - 1] : i++;
        }
    }
    return matches;
}

// LPS trick: check if s is rotation of t
// s + s contains t iff s is rotation of t → KMP(s+s, t)

Z-Algorithm

Z-function — Z[i] = longest match starting at i

function buildZ(s) {
    const n = s.length, z = new Array(n).fill(0);
    z[0] = n;
    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;
}

// Pattern search with Z: build Z(pattern + '#' + text)
// Any Z[i] (in the text part) === pattern.length → match at i
function zSearch(text, pattern) {
    const combined = pattern + '#' + text;
    const z = buildZ(combined);
    const matches = [];
    for (let i = pattern.length + 1; i < combined.length; i++)
        if (z[i] === pattern.length) matches.push(i - pattern.length - 1);
    return matches;
}

Rabin-Karp Rolling Hash

Rolling hash for substring matching

// Hash of window moves in O(1): subtract outgoing char, add incoming char
function rabinKarp(text, pattern) {
    const BASE = 31, MOD = 1_000_000_007;
    const n = text.length, m = pattern.length;
    const matches = [];

    // Precompute powers
    const power = new Array(m + 1).fill(1);
    for (let i = 1; i <= m; i++) power[i] = power[i-1] * BASE % MOD;

    // Hash pattern
    let pHash = 0;
    for (let i = 0; i < m; i++)
        pHash = (pHash * BASE + (pattern.charCodeAt(i) - 96)) % MOD;

    // Rolling hash on text
    let wHash = 0;
    for (let i = 0; i < n; i++) {
        wHash = (wHash * BASE + (text.charCodeAt(i) - 96)) % MOD;
        if (i >= m) {
            wHash = (wHash - (text.charCodeAt(i - m) - 96) * power[m] % MOD + MOD) % MOD;
        }
        if (i >= m - 1 && wHash === pHash) {
            // Verify to avoid collision (O(m) but rare)
            if (text.slice(i - m + 1, i + 1) === pattern) matches.push(i - m + 1);
        }
    }
    return matches;
}