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