String algorithms

The insight: a mismatch still tells you something

The naive substring search tries every alignment and, on a mismatch, throws away everything it just learned — it slides the pattern one step right and re-compares from character zero. That's O(n·m). But a mismatch after k matched characters is not zero information: you now know exactly what the last k characters of the text were, because they were the first k characters of the pattern. Every fast string algorithm in this chapter is a different way of cashing in that information.

The prefix function: what KMP actually precomputes

For a pattern p, define fail[i] as the length of the longest proper prefix of p[0..i] that is also a suffix of p[0..i]. "Proper" means it can't be the whole thing — otherwise the answer would trivially always be i + 1. This single array is all KMP needs: when a mismatch happens after len matched characters, fail[len - 1] tells you the largest number of characters you may keep without re-reading the text.

Building the failure table, step by step

The build is the same algorithm as the search, run with the pattern matched against itself. len holds "how many characters of the prefix currently match the suffix ending at i - 1". On a mismatch you don't reset len to 0 — you fall back to the next shorter candidate, fail[len - 1], and try again.

// prefix function / failure table — O(m) time, O(m) space
function buildFailure(pattern) {
  const fail = new Array(pattern.length).fill(0);
  let len = 0; // length of the current prefix-suffix match

  for (let i = 1; i < pattern.length; i++) { // fail[0] is always 0 — a single char has no proper prefix
    while (len > 0 && pattern[i] !== pattern[len]) {
      len = fail[len - 1]; // fall back to the next-shorter border, don't reset to 0
    }
    if (pattern[i] === pattern[len]) len++;
    fail[i] = len;
  }
  return fail;
}

buildFailure("ababaca"); // [0, 0, 1, 2, 3, 0, 1]

The while loop looks like it could make this quadratic. It can't: len grows by at most 1 per iteration of the outer loop, so across the whole build it increases at most m times — and the while loop only ever decreases it. Total decreases ≤ total increases ≤ m. This is the same amortized argument as the sliding window's left pointer, and it is the sentence to say out loud.

KMP search: the text pointer never moves backward

// all occurrences of pattern in text — O(n + m) time, O(m) space
function kmpSearch(text, pattern) {
  if (pattern.length === 0) return [0];
  const fail = buildFailure(pattern);
  const hits = [];
  let len = 0; // how many pattern chars currently matched

  for (let i = 0; i < text.length; i++) { // i only ever increases — no backtracking in the text
    while (len > 0 && text[i] !== pattern[len]) {
      len = fail[len - 1];
    }
    if (text[i] === pattern[len]) len++;

    if (len === pattern.length) {
      hits.push(i - pattern.length + 1);
      len = fail[len - 1]; // keep going — allows overlapping matches
    }
  }
  return hits;
}

kmpSearch("aaaaa", "aa"); // [0, 1, 2, 3] — overlaps included

Rabin-Karp: compare hashes, not characters

KMP is clever about which comparisons to skip. Rabin-Karp is clever about making each comparison O(1): treat every length-m window of the text as a base-B number mod a large prime, and roll that number forward as the window slides — subtract the outgoing character's contribution, multiply by the base, add the incoming character. A window can only be a match if its hash equals the pattern's hash, so you compare m characters only on a hash hit.

// Rabin-Karp — O(n + m) expected, O(n·m) worst case, O(1) extra space
const BASE = 256;
const MOD = 1000000007; // large prime → collisions are rare, not impossible

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

  let high = 1; // BASE^(m-1) mod MOD — the weight of the leftmost char
  for (let i = 0; i < m - 1; i++) high = (high * BASE) % MOD;

  let patHash = 0, winHash = 0;
  for (let i = 0; i < m; i++) {
    patHash = (patHash * BASE + pattern.charCodeAt(i)) % MOD;
    winHash = (winHash * BASE + text.charCodeAt(i)) % MOD;
  }

  const hits = [];
  for (let i = 0; i + m <= n; i++) {
    // hash equality is necessary but NOT sufficient — always verify
    if (winHash === patHash && text.startsWith(pattern, i)) hits.push(i);

    if (i + m < n) {
      winHash = (winHash - (text.charCodeAt(i) * high) % MOD + MOD) % MOD; // drop the left char (+MOD keeps it non-negative)
      winHash = (winHash * BASE + text.charCodeAt(i + m)) % MOD;           // shift left, add the right char
    }
  }
  return hits;
}

Collisions are handled by the startsWith verification, so Rabin-Karp is never wrong — only occasionally slow. An adversary who knows your BASE and MOD can construct a text where every window collides, degrading it to O(n·m); production implementations pick BASE randomly at startup for exactly this reason. Mentioning that unprompted reads as real experience.

The Z-function: the same information, easier to reason about

z[i] is the length of the longest substring starting at i that is also a prefix of the whole string. It's computed with a "Z-box" — the rightmost interval [l, r] known to match a prefix — which lets you copy an already-known answer from the mirror position instead of recomputing it. Many people find Z easier to derive under pressure than KMP's failure table, and it solves substring search by a trick: concatenate.

// Z-function — O(n) time, O(n) space
function zFunction(s) {
  const n = s.length;
  const z = new Array(n).fill(0);
  z[0] = n;
  let l = 0, r = 0; // [l, r) = rightmost segment known to match a prefix

  for (let i = 1; i < n; i++) {
    if (i < r) z[i] = Math.min(r - i, z[i - l]); // reuse the mirror, clamped to the box
    while (i + z[i] < n && s[z[i]] === s[i + z[i]]) z[i]++; // extend past the box the slow way
    if (i + z[i] > r) { l = i; r = i + z[i]; } // this match reaches further right — adopt it
  }
  return z;
}

// substring search: glue with a separator that appears in neither string
function zSearch(text, pattern) {
  const combined = pattern + "" + text;
  const z = zFunction(combined);
  const hits = [];
  for (let i = pattern.length + 1; i < combined.length; i++) {
    if (z[i] === pattern.length) hits.push(i - pattern.length - 1);
  }
  return hits;
}

The separator must be a character that cannot occur in either string, otherwise a "match" could straddle the boundary and report a false hit. "" is a safe default for arbitrary text; interviewers often accept "#" with a stated assumption.

Manacher's algorithm: every palindrome, in O(n)

Expand-around-center for the longest palindromic substring is O(n²): 2n−1 centers, each expansion up to O(n). Manacher makes it linear with the same reuse idea as the Z-function — a palindrome centered at c reaching to right means positions inside it are mirror images of positions already solved, so you start each expansion from a known lower bound rather than from zero.

First, the unification trick. Odd-length and even-length palindromes need different center handling, which is where most hand-written attempts get tangled. Interleave a separator: "abba" becomes "#a#b#b#a#". The transformed string always has odd length 2n + 1, so every palindrome in it is odd-length and has a single character center — even-length palindromes of the original become odd-length palindromes centered on a #. Better still, the radius p[i] in the transformed string is exactly the palindrome's length in the original string.

// longest palindromic substring — O(n) time, O(n) space
function longestPalindrome(s) {
  if (s.length < 2) return s;

  const t = "#" + s.split("").join("#") + "#"; // always odd length: 2n + 1
  const n = t.length;
  const p = new Array(n).fill(0); // p[i] = palindrome radius at i (= length in s)
  let center = 0, right = 0; // rightmost palindrome found so far

  for (let i = 0; i < n; i++) {
    if (i < right) {
      const mirror = 2 * center - i;
      p[i] = Math.min(right - i, p[mirror]); // clamp: beyond "right" nothing is verified yet
    }
    // expand only past what the mirror already guaranteed
    while (i - p[i] - 1 >= 0 && i + p[i] + 1 < n &&
           t[i - p[i] - 1] === t[i + p[i] + 1]) {
      p[i]++;
    }
    if (i + p[i] > right) { center = i; right = i + p[i]; } // new rightmost reach
  }

  let best = 0, bestCenter = 0;
  for (let i = 0; i < n; i++) {
    if (p[i] > best) { best = p[i]; bestCenter = i; }
  }
  const start = (bestCenter - best) / 2; // map transformed index back to s
  return s.slice(start, start + best);
}

longestPalindrome("babad");   // "bab" (or "aba" — both valid)
longestPalindrome("cbbd");    // "bb"
longestPalindrome("forgeeksskeegfor"); // "geeksskeeg"

That's a genuinely good interview move. Manacher is rarely required — but showing you know the O(n²) baseline, can implement it cleanly, and can explain the linear improvement is worth more than a memorized Manacher you can't justify.

Choosing between them

In real code you would call indexOf, which V8 implements with a tuned hybrid (a two-way / Boyer-Moore-Horspool variant). Say that too — knowing when not to hand-roll is part of the signal. These algorithms earn their keep when the built-in doesn't fit the shape: streaming, multi-pattern, or when the failure table itself is the answer (shortest palindrome, longest repeated prefix, string periodicity).

The failure table answers more than "where is the pattern"

A surprising number of string questions reduce to "compute the prefix function and read one entry."

// Shortest palindrome: prepend the fewest chars to make s a palindrome.
// Trick: the answer hinges on the longest palindromic PREFIX of s.
function shortestPalindrome(s) {
  const rev = s.split("").reverse().join("");
  const fail = buildFailure(s + "" + rev);
  const overlap = fail[fail.length - 1]; // longest prefix of s that is a suffix of reverse(s)
  return rev.slice(0, s.length - overlap) + s;
}

// Smallest repeating unit: "abcabcabc" → "abc". Returns s itself if none.
function repeatedUnit(s) {
  const fail = buildFailure(s);
  const period = s.length - fail[s.length - 1];
  return s.length % period === 0 ? s.slice(0, period) : s;
}

n - fail[n-1] being the smallest period of a string is a genuinely useful identity — it's the whole answer to "Repeated Substring Pattern" and to several string-rotation questions.

Recognizing it in an unseen problem

• "Find all occurrences," "does A contain B," "how many times does the pattern appear" with n and m both large enough that O(n·m) times out — that's KMP or Rabin-Karp
• The input is a stream, or you're told you may not seek backward in the text — KMP is the only one of these that never rewinds the input pointer
• Several patterns, all the same length, searched at once, or a 2D grid pattern — Rabin-Karp, because hashes go into a Set and generalize to rectangles
• Anything about prefixes that are also suffixes, string periodicity, rotations, or "shortest characters to prepend/append" — build the failure table and read one entry, don't invent a new algorithm
• "Longest palindromic substring/prefix," "count all palindromic substrings" — expand-around-center first (O(n²), always acceptable), Manacher if pressed for linear
• Distinguish from DP: "longest palindromic subsequence" (non-contiguous) is 2D DP, not Manacher; "edit distance" and "longest common subsequence" are DP too. These algorithms are all about contiguous matches
• Pitfall: hash equality is never proof of string equality — an implementation that skips the verification step is a bug, not an optimization