KMP / String Matching

How to think about it

Naive matching is O(n*m): for every position, compare the pattern and backtrack on mismatch. KMP eliminates the backtrack with a longest-prefix-suffix (LPS) array: lps[i] is the longest proper prefix of the pattern that is also a suffix of pattern[0..i]. On a mismatch at position j, instead of restarting, jump j to lps[j-1] - you already matched that many characters. Build the LPS array once (O(m)), then scan the text once (O(n)).

Rabin-Karp takes a different route: hash the pattern, then roll a hash across the text. A rolling hash updates in O(1) (subtract the outgoing char, multiply by base, add the incoming char, mod prime). When the hash matches the pattern’s, verify character-by-character (to rule out collisions). It shines when matching multiple patterns (hash set) or when the text is a stream.

Template shapes

Shape	Core move	Example
KMP exact match	Build LPS; scan text with jumps	LC 28
Shortest palindrome	LPS of pattern + reverse(pattern)	LC 214
Longest happy prefix	LPS of the string itself	LC 1392
Rabin-Karp rolling hash	Hash pattern; roll hash across text	LC 3036

Complexity baseline

KMP: O(n + m) time, O(m) space (LPS). Rabin-Karp: O(n + m) average, O(n*m) worst case (many collisions); use a double hash to make collisions negligible. Rolling hash update: O(1).

From template to problem

1. Is it exact single-pattern matching? → KMP. Multiple patterns or sliding? → Rabin-Karp.
2. Build the LPS array carefully, the lps[i] is the prefix length before i, not at i.
3. For Rabin-Karp, pick a base > alphabet size and a large prime; take mod at every step.
4. Always verify a hash match with a character check before returning.

/** KMP template: build LPS array and find pattern in text. */

export function buildLps(pattern: string): number[] {
  const lps = new Array<number>(pattern.length).fill(0);
  let len = 0;
  for (let i = 1; i < pattern.length; i++) {
    while (len > 0 && pattern[i] !== pattern[len]) len = lps[len - 1]!;
    if (pattern[i] === pattern[len]) len++;
    lps[i] = len;
  }
  return lps;
}

export function kmpSearch(text: string, pattern: string): number {
  if (pattern.length === 0) return 0;
  const lps = buildLps(pattern);
  let j = 0;
  for (let i = 0; i < text.length; i++) {
    while (j > 0 && text[i] !== pattern[j]) j = lps[j - 1]!;
    if (text[i] === pattern[j]) j++;
    if (j === pattern.length) return i - j + 1;
  }
  return -1;
}

/** KMP template: build LPS array and find pattern in text. */

export function buildLps(pattern: string): number[] {
  const lps = new Array<number>(pattern.length).fill(0);
  let len = 0;
  for (let i = 1; i < pattern.length; i++) {
    while (len > 0 && pattern[i] !== pattern[len]) len = lps[len - 1]!;
    if (pattern[i] === pattern[len]) len++;
    lps[i] = len;
  }
  return lps;
}

export function kmpSearch(text: string, pattern: string): number {
  if (pattern.length === 0) return 0;
  const lps = buildLps(pattern);
  let j = 0;
  for (let i = 0; i < text.length; i++) {
    while (j > 0 && text[i] !== pattern[j]) j = lps[j - 1]!;
    if (text[i] === pattern[j]) j++;
    if (j === pattern.length) return i - j + 1;
  }
  return -1;
}