DSAPattern Matching (KMP, Rabin-Karp)

Pattern Matching (KMP, Rabin-Karp)

Pattern matching is the problem of finding all occurrences of a short string (needle / pattern) inside a longer string (haystack / text).

  • Text length: n
  • Pattern length: m

The naive algorithm runs in O(n·m). KMP and Rabin-Karp both achieve O(n + m) — but through completely different ideas. Knowing when to reach for each one is what interviewers test.

Naive Brute Force — O(n·m)

Try every possible starting position in the text; at each position compare the pattern character-by-character. Simple but slow — in the worst case (e.g. text = "aaaa…a", pattern = "aaa…ab") every alignment fails on the last character after m comparisons.

JS
function naiveSearch(text, pattern) {
  const n = text.length, m = pattern.length;
  const matches = [];

  for (let i = 0; i <= n - m; i++) {
    let j = 0;
    while (j < m && text[i + j] === pattern[j]) j++;
    if (j === m) matches.push(i); // full match at index i
  }
  return matches;
}

console.log(naiveSearch('abcabcabc', 'abc')); // [0, 3, 6]
console.log(naiveSearch('aaaa', 'aa'));        // [0, 1, 2]
KMP — Knuth-Morris-Pratt

KMP eliminates redundant comparisons by pre-computing a failure function (also called the partial-match table or LPS — Longest Proper Prefix that is also a Suffix).

When a mismatch occurs at position j in the pattern, instead of restarting from scratch, we jump to lps[j-1]. This means we never move the text pointer backwards.

Step 1 — Build the LPS (Failure Function)

lps[i] = length of the longest proper prefix of pattern[0..i] that is also a suffix. "Proper" means the prefix cannot be the entire string.

JS
// pattern = "abacaba"
// lps    = [0, 0, 1, 0, 1, 2, 3]
//
// lps[6] = 3 because "aba" is both a prefix and suffix of "abacaba"

function buildLPS(pattern) {
  const m = pattern.length;
  const lps = new Array(m).fill(0);
  let len = 0; // length of previous longest prefix-suffix
  let i = 1;

  while (i < m) {
    if (pattern[i] === pattern[len]) {
      lps[i] = ++len;
      i++;
    } else if (len !== 0) {
      // Don't increment i — try a shorter prefix
      len = lps[len - 1];
    } else {
      lps[i] = 0;
      i++;
    }
  }
  return lps;
}

console.log(buildLPS('abacaba'));  // [0,0,1,0,1,2,3]
console.log(buildLPS('aabaabaaa')); // [0,1,0,1,2,3,4,5,2]
Step 2 — KMP Search

JS
function kmpSearch(text, pattern) {
  const n = text.length, m = pattern.length;
  if (m === 0) return [0];

  const lps = buildLPS(pattern);
  const matches = [];
  let i = 0; // text index
  let j = 0; // pattern index

  while (i < n) {
    if (text[i] === pattern[j]) {
      i++;
      j++;
    }

    if (j === m) {
      matches.push(i - j); // match found
      j = lps[j - 1];      // look for next match using failure function
    } else if (i < n && text[i] !== pattern[j]) {
      if (j !== 0) {
        j = lps[j - 1]; // shift pattern, don't move i
      } else {
        i++;
      }
    }
  }
  return matches;
}

console.log(kmpSearch('abcabcabc', 'abc')); // [0, 3, 6]
console.log(kmpSearch('aabxaabyaab', 'aab')); // [0, 4, 8]
Note
KMP Time: O(n + m). Space: O(m) for the LPS array. The text pointer i never moves backward — that is the core guarantee that makes it linear.
Rabin-Karp — Rolling Hash

Rabin-Karp avoids character-by-character comparison by turning each window of length m into a hash value and comparing hashes instead.

The trick is a rolling hash: when the window slides one step right, you can compute the new hash in O(1) by:

  1. Subtracting the contribution of the leftmost character,
  2. Multiplying by the base,
  3. Adding the new rightmost character.

A hash match is followed by a full character comparison to rule out hash collisions.

JS
function rabinKarp(text, pattern) {
  const n = text.length, m = pattern.length;
  if (m > n) return [];

  const BASE = 31;
  const MOD  = 1_000_000_007n; // use BigInt to avoid JS float overflow
  const base = BigInt(BASE);
  const mod  = MOD;
  const a    = BigInt('a'.charCodeAt(0) - 1);

  // Precompute base^(m-1) mod MOD
  let power = 1n;
  for (let i = 0; i < m - 1; i++) power = (power * base) % mod;

  // Hash of a single string window
  function hash(s, start, len) {
    let h = 0n;
    for (let i = 0; i < len; i++) {
      h = (h * base + BigInt(s.charCodeAt(start + i)) - a + 1n) % mod;
    }
    return h;
  }

  let patHash  = hash(pattern, 0, m);
  let winHash  = hash(text, 0, m);
  const matches = [];

  for (let i = 0; i <= n - m; i++) {
    if (winHash === patHash) {
      // Hash match — verify with full comparison to handle collisions
      if (text.slice(i, i + m) === pattern) matches.push(i);
    }
    if (i < n - m) {
      // Roll the hash one step right
      winHash = (
        (winHash - (BigInt(text.charCodeAt(i)) - a + 1n) * power % mod + mod)
        * base
        + BigInt(text.charCodeAt(i + m)) - a + 1n
      ) % mod;
    }
  }
  return matches;
}

console.log(rabinKarp('abcabcabc', 'abc')); // [0, 3, 6]
Warning
Rabin-Karp average complexity is O(n + m) but worst-case is O(n·m) when every window produces a hash collision. Choose a large prime modulus (and ideally double-hash) to make this astronomically unlikely in practice.
Z-Algorithm

The Z-algorithm computes a Z-array where Z[i] is the length of the longest substring starting at i that is also a prefix of the string.

To find pattern P in text T, concatenate P + '$' + T (the $ acts as a sentinel that cannot appear in either string), compute the Z-array, and every position where Z[i] === m is a match.

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

function zSearch(text, pattern) {
  const combined = pattern + '$' + text;
  const Z = zArray(combined);
  const m = pattern.length;
  const matches = [];

  for (let i = m + 1; i < combined.length; i++) {
    if (Z[i] === m) matches.push(i - m - 1); // offset back into text
  }
  return matches;
}

console.log(zSearch('aabxaab', 'aab')); // [0, 4]
When to Use Each Algorithm

Algorithm

Best for

Avg Time

Worst Time

Space

Naive

Short strings / interview warm-up

O(n+m)

O(n·m)

O(1)

KMP

Single pattern search, repeated queries on same pattern

O(n+m)

O(n+m)

O(m)

Rabin-Karp

Multi-pattern search (hash many patterns at once)

O(n+m)

O(n·m)

O(m)

Z-Algorithm

Pattern in string, prefix-suffix queries

O(n+m)

O(n+m)

O(n+m)

Tip
For interview problems use KMP when asked to "implement indexOf" in O(n+m). Use Rabin-Karp when asked to detect any of multiple patterns simultaneously. The Z-algorithm is elegant for problems about prefixes and suffixes of the same string.
Practice Problems

  • LeetCode 28 — Find the Index of the First Occurrence in a String (KMP)

  • LeetCode 459 — Repeated Substring Pattern (KMP / Z-algorithm)

  • LeetCode 686 — Repeated String Match (rotation + KMP)

  • LeetCode 1392 — Longest Happy Prefix (build LPS array directly)

  • LeetCode 214 — Shortest Palindrome (KMP on reversed string)