String Matching: KMP and Rabin-Karp

Searching for a substring is O(n × m) if you do the obvious thing. Two classic algorithms get it to O(n + m), each by never throwing away what the previous comparison already told you.

Why the naive version is slow

Line the pattern up at position 0, compare characters until one differs, shift right by one, start over. Each restart forgets everything learned, and on adversarial input - a long run of the same character - it degrades to comparing nearly every pair.

function naiveSearch(text, pattern) {
  for (let i = 0; i + pattern.length <= text.length; i++) {
    let j = 0
    while (j < pattern.length && text[i + j] === pattern[j]) j++
    if (j === pattern.length) return i
  }
  return -1
}

// Worst case: "aaaaaaaaab" searched for "aaab" restarts on every position.
console.log(naiveSearch("aaaaaaaaab", "aaab"))  // 6

KMP: never re-compare a prefix

If the first six characters matched and the seventh did not, you already know what those six were. KMP precomputes, for every position in the pattern, the length of the longest proper prefix that is also a suffix - so on a mismatch it can jump the pattern forward without moving backwards through the text at all.

function buildFailure(pattern) {
  const fail = new Array(pattern.length).fill(0)
  let length = 0

  for (let i = 1; i < pattern.length; i++) {
    while (length > 0 && pattern[i] !== pattern[length]) {
      length = fail[length - 1]
    }
    if (pattern[i] === pattern[length]) length++
    fail[i] = length
  }

  return fail
}

function kmpSearch(text, pattern) {
  if (!pattern) return 0
  const fail = buildFailure(pattern)
  let matched = 0

  for (let i = 0; i < text.length; i++) {
    while (matched > 0 && text[i] !== pattern[matched]) {
      matched = fail[matched - 1]
    }
    if (text[i] === pattern[matched]) matched++
    if (matched === pattern.length) return i - pattern.length + 1
  }

  return -1
}

console.log(kmpSearch("ababcabcabababd", "ababd"))  // 10

The index i only ever increases, which is what guarantees O(n + m): the text is scanned once, and the table is built once.

Rabin-Karp: compare hashes, not characters

Hash the pattern, then hash each window of the text and compare numbers. A rolling hash updates in O(1) per shift - remove the outgoing character's contribution, add the incoming one - so the whole scan is linear.

Hashes can collide, so a match must be confirmed by an actual character comparison. That makes the worst case O(n × m), but with a sensible modulus it effectively never happens.

Which to use

• One pattern, one text - indexOf. Engine-optimised and almost certainly faster than anything you write.
• Guaranteed linear worst case required - KMP.
• Many patterns at once, or 2D grid search - Rabin-Karp, since all patterns of the same length share one rolling hash.
• Asked in an interview - say indexOf exists, then implement the one they want.