String Matching Algorithms

"KMP: O(n+m) search using failure function. Rabin-Karp: hash-based. Z-algorithm: substring in O(n)."

String pattern matching goes from O(n·m) brute force to O(n+m) with KMP. Learn the KMP failure function (LPS array), Z-algorithm for all prefix-suffix matches, and Rabin-Karp for multi-pattern hashing. Used in autocomplete, plagiarism detection, DNA matching.

20 min readstring problems →

Problems you can solve with this pattern

6 problems · click any to start solving

All string →

1Find the Index of the First Occurrence in a StringEasySolve

2Repeated Substring PatternEasySolve

3Shortest PalindromeHardSolve

4Count Occurrences of AnagramMediumSolve

KMP — O(n + m) pattern search

// Build LPS (Longest Proper Prefix = Suffix) array for pattern
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]; // backtrack using LPS (don't reset i)
        } else {
            lps[i++] = 0;
        }
    }
    return lps;
}

// Search for all occurrences of pattern in text
function kmpSearch(text, pattern) {
    const lps = buildLPS(pattern);
    const positions = [];
    let i = 0, j = 0; // i = text index, j = pattern index
    while (i < text.length) {
        if (text[i] === pattern[j]) {
            i++; j++;
        }
        if (j === pattern.length) {
            positions.push(i - j); // found match at position i-j
            j = lps[j - 1];        // continue searching
        } else if (i < text.length && text[i] !== pattern[j]) {
            if (j > 0) j = lps[j - 1]; // skip using LPS
            else i++;
        }
    }
    return positions;
}

String matching asks: does pattern P appear in text T? The brute force tries every position in T and checks character by character — O(n·m). The key insight behind KMP: when a mismatch occurs, we've already matched some prefix of P. That prefix tells us how far we can skip without missing a match. This "partial match" information is precomputed into the LPS (Longest Proper Prefix which is also Suffix) array.

KMP Algorithm

LPS array (failure function): lps[i] = length of longest proper prefix of pattern[0..i] that is also a suffix.

Example: pattern = "AAACAAAA"
lps = [0, 1, 2, 0, 1, 2, 3, 3]

During matching: on mismatch at pattern[j], DON'T reset j to 0. Instead j = lps[j-1]. This skips positions we already know match.

KMP — O(n + m) pattern search

// Build LPS (Longest Proper Prefix = Suffix) array for pattern
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]; // backtrack using LPS (don't reset i)
        } else {
            lps[i++] = 0;
        }
    }
    return lps;
}

// Search for all occurrences of pattern in text
function kmpSearch(text, pattern) {
    const lps = buildLPS(pattern);
    const positions = [];
    let i = 0, j = 0; // i = text index, j = pattern index
    while (i < text.length) {
        if (text[i] === pattern[j]) {
            i++; j++;
        }
        if (j === pattern.length) {
            positions.push(i - j); // found match at position i-j
            j = lps[j - 1];        // continue searching
        } else if (i < text.length && text[i] !== pattern[j]) {
            if (j > 0) j = lps[j - 1]; // skip using LPS
            else i++;
        }
    }
    return positions;
}

Z-Algorithm

Z-array: z[i] = length of the longest substring starting at position i that is also a prefix of the string.

z[0] is undefined (or set to n by convention).
z[1] = length of longest prefix of s that matches s[1..]

Pattern matching with Z: Concatenate pattern + '$' + text. Build Z-array. Any Z[i] >= len(pattern) means pattern found at position i - len(pattern) - 1 in text.

Z-algorithm — O(n)

function buildZ(s) {
    const n = s.length, 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;
}

// Find all pattern occurrences using Z-algorithm
function zSearch(text, pattern) {
    const s = pattern + '$' + text; // separator prevents match across boundary
    const z = buildZ(s);
    const positions = [], m = pattern.length;
    for (let i = m + 1; i < s.length; i++)
        if (z[i] >= m) positions.push(i - m - 1); // found at text position i-m-1
    return positions;
}

Rabin-Karp (Rolling Hash)

Rabin-Karp — O(n) average, O(nm) worst case

// Rolling hash for substring search
function rabinKarp(text, pattern) {
    const BASE = 31, MOD = 1_000_000_007;
    const n = text.length, m = pattern.length;

    // Hash of pattern
    let patHash = 0, pow = 1;
    for (let i = 0; i < m; i++) {
        patHash = (patHash + (pattern.charCodeAt(i) - 96) * pow) % MOD;
        if (i < m - 1) pow = pow * BASE % MOD;
    }

    // Hash of first window, then slide
    let winHash = 0, positions = [];
    for (let i = 0; i < n; i++) {
        winHash = (winHash + (text.charCodeAt(i) - 96) * (i < m ? pow : 1)) % MOD;
        if (i >= m) {
            // Remove leftmost character
            winHash = (winHash - (text.charCodeAt(i-m) - 96) + MOD) % MOD;
            winHash = winHash * modInverse(BASE, MOD) % MOD; // divide by BASE
        }
        if (i >= m - 1 && winHash === patHash) {
            // Hash match: verify (handles collisions)
            if (text.slice(i - m + 1, i + 1) === pattern)
                positions.push(i - m + 1);
        }
    }
    return positions;
}

// Easier rolling hash: add new char, remove old char
// Rabin-Karp shines for MULTIPLE patterns: hash all patterns, single pass over text

Find the Index of the First Occurrence in a String

Easy

Solve

Repeated Substring Pattern

Easy

Solve

Shortest Palindrome

Hard

Solve

Count Occurrences of Anagram

Medium

Solve

Longest Happy Prefix (KMP LPS application)

Hard

Solve

Implement strStr (Rabin-Karp variant)

Easy

Solve

String matching algorithm selector:
- Single pattern in text → KMP (O(n+m), deterministic)
- Multiple patterns in text → Aho-Corasick (build trie of all patterns, single pass)
- Substring comparison / all prefix-suffix matches → Z-algorithm
- Rolling hash / multiple patterns / competitive → Rabin-Karp
- "Repeated substring" / "palindrome prefix" → LPS/KMP tricks
- "Longest prefix = suffix" → lps[n-1] (KMP LPS last value)

← Prefix Sum & Difference Array HashMap & Counting Patterns →