String matching

Overview

String matching finds occurrences of a pattern of length m inside a text of length n. The naive approach checks every starting position and costs O(n x m) in the worst case. Linear-time algorithms avoid re-examining characters by preprocessing the pattern.

KMP (Knuth-Morris-Pratt) builds an LPS array: for each prefix of the pattern, the length of its longest proper prefix that is also a suffix. On a mismatch, it jumps the pattern forward using that array instead of restarting, giving O(n + m). The Z-algorithm and rolling hashes (Rabin-Karp) are the other common linear approaches.

When to use it

• Find the first or all occurrences of a pattern in text.
• Repeated or periodic structure in a string (repeated substring pattern).
• Shortest palindrome and prefix-suffix problems.
• Large inputs where O(n x m) is too slow.

Problem patterns it solves

Where it is used in real software

Key terms

LPS array

lps[i] = length of the longest proper prefix of pattern[0..i] that is also a suffix.

Proper prefix

A prefix that is not the whole string.

Z-array

z[i] = length of the longest substring starting at i that matches a prefix.

Boyer-Moore

Compares from the pattern's end and skips ahead using bad-character rules; fast in practice.

KMP in two phases

1. 1
   Build LPS

   Walk the pattern with len = current matched prefix length. On match, len++ and lps[i] = len. On mismatch, fall back len = lps[len - 1] (or set 0).

2. 2
   Search

   Walk the text with j = number of pattern characters matched.

3. 3
   Match

   If text[i] === pattern[j], advance both; if j === m, a match ends at i.

4. 4
   Mismatch

   If j > 0, set j = lps[j - 1] and retry the same text character. Otherwise advance i.

5. 5
   Never move the text pointer backward

   That is why the total is O(n + m).

LPS array for pattern "ABABCABAB"

lps[i] = longest proper prefix of pattern[0..i] that is also its suffix

After matching the whole pattern, KMP continues as if 4 characters (ABAB) are already matched, so it finds overlapping occurrences without rescanning the text. On a mismatch after matching ABABCABA (8 characters), it resumes with lps[7] = 3 characters matched.

Implementation

1function buildLPS(pattern) {2  const lps = new Array(pattern.length).fill(0);3  let len = 0;4  for (let i = 1; i < pattern.length; ) {5    if (pattern[i] === pattern[len]) {6      lps[i++] = ++len;7    } else if (len > 0) {8      len = lps[len - 1]; // try a shorter border9    } else {10      lps[i++] = 0;11    }12  }13  return lps;14}15 16function kmpSearch(text, pattern) {17  if (!pattern) return [0];18  const lps = buildLPS(pattern);19  const matches = [];20  let j = 0;21  for (let i = 0; i < text.length; i++) {22    while (j > 0 && text[i] !== pattern[j]) j = lps[j - 1];23    if (text[i] === pattern[j]) j++;24    if (j === pattern.length) {25      matches.push(i - j + 1);26      j = lps[j - 1]; // continue for overlapping matches27    }28  }29  return matches;30}31 32// 459. Repeated Substring Pattern using LPS33function repeatedSubstringPattern(s) {34  const lps = buildLPS(s);35  const border = lps[s.length - 1];36  const period = s.length - border;37  return border > 0 && s.length % period === 0;38}39 40// 214. Shortest Palindrome: longest palindromic prefix via LPS of s + '#' + reverse(s)41function shortestPalindrome(s) {42  const rev = [...s].reverse().join("");43  const lps = buildLPS(s + "#" + rev);44  return rev.slice(0, s.length - lps.at(-1)) + s;45}

Complexity and performance

Trade-offs

Variants and related techniques

Common mistakes

• Advancing i after a fallback in the LPS build.

  Fix: When len = lps[len - 1], stay on the same i and compare again.

• Missing overlapping matches.

  Fix: After a full match set j = lps[j - 1], not 0.

• Separator collisions in combined strings.

  Fix: Use a character that cannot appear in the input (#, $).

Interview questions

Practice problems