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]

Dry run: buildFailure("ababaca")

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 [];
  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.

Prefix hashes: compare any two substrings in O(1)

The rolling hash above slides one fixed-length window. Many problems instead ask "are these two substrings equal?" for arbitrary positions and lengths, again and again. Comparing characters costs O(length) each time. The fix is to precompute a hash of every prefix once, so the hash of any substring becomes a subtraction.

Let H[i] be the hash of the first i characters, built left to right: H[0] = 0 and H[i + 1] = H[i] · B + code(s[i]) (mod p). Unrolling the recurrence, H[r] is the polynomial whose highest power of B multiplies s[0]. The first l characters contribute H[l] multiplied by B once for each of the r − l characters that follow them, so

hash(s[l..r)) = H[r] − H[l] · B^r−l (mod p)

Two substrings of the same length are equal exactly when their hashes are equal, up to collisions. A small worked example with base 10, modulus 101 and a = 1, b = 2 on "abab": the prefix hashes are H = [0, 1, 12, 20, 0]. The substring "ab" at [0, 2) has hash 12 − 0 · 100 = 12. The one at [2, 4) has hash 0 − 12 · 100 = −1200, which is 12 modulo 101 (since 1200 = 11 · 101 + 89 and 101 − 89 = 12). Equal, as they should be.

// (a * b) % mod without leaving the exact integer range; needs 0 <= a, b < mod < 2^31
function mulMod(a, b, mod) {
  const high = Math.floor(b / 65536); // b = high * 65536 + low
  const low = b % 65536;
  return (((a * high) % mod) * 65536 + a * low) % mod;
}

// two independent hashes of every prefix, so substring hashes cost O(1) after O(n) setup
class SubstringHasher {
  constructor(s) {
    const n = s.length;
    this.mods = [1000000007, 998244353];
    this.prefix = [];
    this.power = [];
    for (const mod of this.mods) {
      const base = 256 + Math.floor(Math.random() * (mod - 512)); // random base, chosen at run time
      const prefix = new Array(n + 1).fill(0);
      const power = new Array(n + 1).fill(1); // power[i] = base^i mod mod
      for (let i = 0; i < n; i++) {
        prefix[i + 1] = (mulMod(prefix[i], base, mod) + s.charCodeAt(i)) % mod;
        power[i + 1] = mulMod(power[i], base, mod);
      }
      this.prefix.push(prefix);
      this.power.push(power);
    }
  }

  // hash of s[l..r), as a string key that is safe to use in a Map
  hash(l, r) {
    const parts = this.mods.map((mod, k) => {
      const removed = mulMod(this.prefix[k][l], this.power[k][r - l], mod);
      return (this.prefix[k][r] - removed + mod) % mod; // + mod keeps the difference non-negative
    });
    return parts.join(",");
  }
}

Setup is O(n) time and space; every hash(l, r) after that is O(1) (two mulMod calls). Two independent moduli are used for a reason explained two sections below. The hash is returned as a string such as "123456,789012" because the two numbers together are too large to pack into one exact Number.

Longest duplicate substring: binary search on the length

Find the longest substring that occurs at least twice (the two copies may overlap). Checking every pair of start positions with a character comparison is O(n³) in the worst case. Two observations make it O(n log n).

• Monotone in the length. If some substring of length L occurs twice, so does its first L − 1 characters. So "is there a duplicate of length L?" is true for small L and false from some point on, which is exactly the shape binary search needs.
• One length is one pass. For a fixed L, slide a window over the string, hash every window in O(1) with the prefix hashes, and store the hashes in a Map. The first window whose hash is already present is a candidate duplicate.

// O(n log n) expected time, O(n) space. Overlapping copies count; any longest one may be returned.
function longestDupSubstring(s) {
  const n = s.length;
  const hasher = new SubstringHasher(s);

  // start of the second copy of some repeated substring of this length, or -1
  function duplicateStart(len) {
    const seen = new Map(); // hash key -> starts of windows with that hash
    for (let i = 0; i + len <= n; i++) {
      const key = hasher.hash(i, i + len);
      const starts = seen.get(key);
      if (starts === undefined) {
        seen.set(key, [i]);
        continue;
      }
      const here = s.slice(i, i + len);
      if (starts.some((j) => s.startsWith(here, j))) return i; // verify: equal hashes may still be a collision
      starts.push(i);
    }
    return -1;
  }

  let lo = 1, hi = n - 1, best = "";
  while (lo <= hi) {
    const mid = (lo + hi) >> 1;
    const at = duplicateStart(mid);
    if (at !== -1) {
      best = s.slice(at, at + mid); // a duplicate exists: remember it and try longer
      lo = mid + 1;
    } else {
      hi = mid - 1;
    }
  }
  return best;
}

Dry run: longestDupSubstring("banana")

Cost: about log n rounds, each one pass of n window hashes, each O(1), plus the verification. Verification happens only on a hash hit, and a true hit ends the round immediately, so it adds O(L) once per round in the usual case: the total expected time stays O(n log n). Correctness never depends on luck: a collision costs time (an extra comparison), never a wrong answer.

Double hashing, and the hash that anyone can break

A single modulus near 10⁹ has only about a billion possible hash values. By the birthday paradox, among about the square root of that many different strings (tens of thousands) two will probably share a hash. In longestDupSubstring that is harmless, because it verifies, but in code that trusts the hash to mean equality it is a real bug waiting for a big input. Double hashing uses two independent moduli (and bases) and treats two substrings as equal only if both hashes agree. The combined space is about 10¹⁸ values, so the collision probability among 10⁵ strings, roughly (10⁵)² / 2 divided by 10¹⁸, is about 5 × 10⁻⁹.

The other defence is where the base comes from. If the base and modulus are constants in the source, anyone who can read the problem can construct inputs that collide on purpose. Choosing the base at run time, as SubstringHasher does, means a test written in advance cannot target it.

The most instructive failure is the one with no modulus at all. Hashing with the machine's natural 32-bit overflow looks harmless, and it is trivial to break. Build two strings by the Thue–Morse rule: start from T = "a" and S = "b", and repeat T, S = T + S, S + T. After seven rounds the two strings are 128 characters long and differ in every position (one is the other with a and b swapped), and yet they have exactly the same hash for every odd base:

function overflowHash(s, base) {
  let h = 0;
  for (let i = 0; i < s.length; i++) h = (Math.imul(h, base) + s.charCodeAt(i)) | 0; // wraps at 2^32
  return h;
}

function thueMorsePair(rounds) {
  let t = "a", u = "b";
  for (let i = 0; i < rounds; i++) [t, u] = [t + u, u + t];
  return [t, u];
}

const [t, u] = thueMorsePair(7);
t === u;                                 // false, 128 characters each
overflowHash(t, 31) === overflowHash(u, 31); // true, for any odd base

The reason is that the difference of the two hashes is, up to sign, a product of factors B2i − 1, each divisible by a growing power of two, so after a few rounds it is divisible by 2³² and vanishes. (We checked every odd base below 20,000.) With a 64-bit wrap the same construction needs only ten rounds, 1,024 characters. A prime modulus does not have this weakness, which is why the code uses one.

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;
  if (n === 0) return [];
  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 assumed to appear in neither string
function zSearch(text, pattern) {
  if (pattern.length === 0) return [];
  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. If it does, a prefix match can run across the boundary, z[i] exceeds pattern.length, and the === test misses a real hit: zSearch("a#", "a") returns []. This code uses "#", so it assumes the strings hold no # (lowercase letters, say); state that assumption out loud, and pick another character if the input can contain one. All three searchers here (kmpSearch, rabinKarp, zSearch) return [] for an empty pattern, a choice to state aloud, since indexOf("") would call it a match at 0.

Sum of scores: reading the whole Z array

The Z-function gives you, for every position, how far the string agrees with its own beginning. Some problems ask for an aggregate of that. Here is one. Build a string by prepending characters one at a time, so the strings are the suffixes of s of length 1, 2, ..., n. The score of a suffix is the length of its longest common prefix with the full string s. What is the sum of the scores of all n suffixes?

The suffix of length i starts at position n − i, and its score is exactly z[n − i], the length of the longest match with the prefix there. As i runs from 1 to n, the position n − i runs through every index of the string, so the answer is the sum of the whole Z array. The suffix of length n is the string itself and scores n, which is why zFunction sets z[0] = n.

// O(n) time, O(n) space; uses zFunction from above
function sumScores(s) {
  return zFunction(s).reduce((total, value) => total + value, 0);
}

sumScores("babab"); // 9

The scores 5 + 0 + 3 + 0 + 1 add up to 9. The brute force, comparing every suffix against the string character by character, is O(n²) in the worst case ("aaaa..."). The Z array does all those comparisons in one linear pass. The same sum counts, over all lengths k, how many positions the prefix of length k occurs at, so "how many times does each prefix occur" is also one read of the Z array: the number of occurrences of the length-k prefix is the number of positions with z[i] >= k.

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 engines implement with a tuned hybrid (V8's is Boyer-Moore-Horspool based). 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;
}

As in zSearch, the "#" in shortestPalindrome must not occur in s: if it does, the table's last entry can exceed s.length and the answer is wrong, as shortestPalindrome("a#a") shows.

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

Why the prefix function finds the longest palindromic prefix

shortestPalindrome above is short enough to look like a trick. Here is the reasoning that makes it a method. To make s a palindrome by adding characters only at the front, you keep the longest prefix of s that is already a palindrome, P, and mirror everything after it onto the front. The cost is the length of the part that is not in P, so the whole problem is to find the longest palindromic prefix.

Now connect that to borders. The suffix of reverse(s) of length k is the reverse of the prefix of s of length k. A string is a palindrome exactly when it equals its own reverse. So the prefix of length k is a palindrome if and only if it equals the length-k suffix of reverse(s). In s + "#" + reverse(s), that says the length-k prefix of the whole string equals its length-k suffix, which is a border, and the last entry of the prefix function is the length of the longest border. The # keeps the border from being longer than n, because no match can contain it (it occurs once).

Dry run: s = "aacecaaa", rev = "aaacecaa", glued = "aacecaaa#aaacecaa"

The last value is 7, so "aacecaa" (the first seven characters) is the longest palindromic prefix. The characters left over are s.slice(7) = "a"; its reverse is prepended, and the result is "a" + "aacecaaa" = "aaacecaaa". In code, rev.slice(0, n - overlap) is that reversed leftover. The method is O(n) where checking every prefix for being a palindrome is O(n²). The same idea, with the roles of prefix and suffix swapped, gives the shortest string to append.

Minimal rotation: the smallest cyclic shift

A rotation moves a prefix to the end: the rotations of "bca" are "bca", "cab" and "abc". Two questions come up. Is t a rotation of s? And what is the lexicographically smallest rotation of s, a canonical form that lets you compare cyclic strings or group strings that are rotations of each other?

The first has a clean answer: t is a rotation of s exactly when the lengths match and t occurs inside s + s, because every rotation of s is a window of length n in s + s. With KMP that is O(n):

// O(n) time using kmpSearch from above
function isRotation(s, t) {
  return s.length === t.length && (s.length === 0 || kmpSearch(s + s, t).length > 0);
}

For the smallest rotation, trying all n rotations and comparing them costs O(n²). The two-pointer method below does it in O(n). Keep two candidate starts, i and j, and compare the rotations that begin at them, character by character, with k counting how many characters agree. At the first difference:

• If the character at i + k is larger, the rotation starting at i is not minimal. Neither is any start in (i, i + k]: the start i + t is dominated by the start j + t, which matched the same characters and is at least as small afterwards. Move i to i + k + 1.
• If it is smaller, the same argument applies to j.

// start index of the lexicographically smallest rotation — O(n) time, O(1) space
function minimalRotationStart(s) {
  const n = s.length;
  let i = 0, j = 1, k = 0;
  while (i < n && j < n && k < n) {
    const a = s[(i + k) % n], b = s[(j + k) % n]; // the % n is what makes the string circular
    if (a === b) { k++; continue; }
    if (a > b) i += k + 1;
    else j += k + 1;
    if (i === j) j++; // the candidates must stay different
    k = 0;
  }
  return Math.min(i, j);
}

function minimalRotation(s) {
  const at = minimalRotationStart(s);
  return s.slice(at) + s.slice(0, at);
}

minimalRotation("bca");   // "abc"
minimalRotation("cabab"); // "ababc"

Dry run: minimalRotationStart("cabab")

Each comparison either raises k or, on a mismatch, moves one pointer forward by k + 1, so the pointers advance at least as far as the work done, and each can only go up to about n. The total is O(n). Use it for "group the strings that are rotations of each other" by keying on minimalRotation(s), and for any cyclic comparison.

Aho-Corasick: many patterns, one pass over the text

KMP finds one pattern. A list of banned words, a dictionary of keywords, or a set of DNA motifs needs all of them at once. Running KMP once per pattern costs O(k · n) for k patterns. A trie of all patterns plus the idea behind KMP's failure table gives one pass over the text: Aho-Corasick.

Start from the trie of the patterns (see the tries chapter). The state is the trie node for the longest suffix of the text read so far that is a prefix of some pattern. When the next character has no edge from the node, KMP would fall back to a shorter border. Here the node falls back along a failure link: the link of a node is the trie node for the longest proper suffix of its string that is also a prefix of some pattern. Links are computed in breadth-first order, so a node's link points to a shallower node that is already done. One more detail: a pattern can end inside another one ("he" inside "she"), so each node also collects the patterns that end at the nodes along its failure chain.

// patterns must be non-empty. O(total pattern length) to build, using Maps for transitions.
function buildAhoCorasick(patterns) {
  const next = [new Map()]; // next[node]: character -> child node
  const link = [0];         // failure link of each node; the root links to itself
  const out = [[]];         // out[node]: ids of patterns that END at this node or on its failure chain

  patterns.forEach((word, id) => {
    let node = 0;
    for (const ch of word) {
      if (!next[node].has(ch)) {
        next[node].set(ch, next.length);
        next.push(new Map());
        link.push(0);
        out.push([]);
      }
      node = next[node].get(ch);
    }
    out[node].push(id);
  });

  const queue = [...next[0].values()]; // depth-1 nodes keep link 0
  for (let head = 0; head < queue.length; head++) {
    const node = queue[head];
    for (const [ch, child] of next[node]) {
      let f = link[node];
      while (f !== 0 && !next[f].has(ch)) f = link[f]; // the KMP fallback, on the trie
      link[child] = next[f].has(ch) ? next[f].get(ch) : 0;
      out[child] = out[child].concat(out[link[child]]); // the link is shallower, so its list is already complete
      queue.push(child);
    }
  }
  return { next, link, out };
}

// every occurrence as [startIndex, patternId] — O(text length + matches) after the build
function ahoCorasickSearch(text, patterns) {
  const { next, link, out } = buildAhoCorasick(patterns);
  const hits = [];
  let node = 0;
  for (let i = 0; i < text.length; i++) {
    const ch = text[i];
    while (node !== 0 && !next[node].has(ch)) node = link[node];
    if (next[node].has(ch)) node = next[node].get(ch);
    for (const id of out[node]) hits.push([i - patterns[id].length + 1, id]);
  }
  return hits;
}

ahoCorasickSearch("ushers", ["he", "she", "his", "hers"]); // [[1, 1], [2, 0], [2, 3]]

Dry run: patterns he, she, his, hers, text "ushers"

The trie has ten nodes. The ones that matter for the search:

Both she and he are reported at index 3 even though only one trie node was reached, because out[she] inherited he through the failure link. The transition from she on r is the interesting one: the text so far, "ushe", ends in "he", which is exactly where a continuation "r" can still lead to "hers". KMP would have called that falling back to a border.

Complexity: the node pointer can rise by one level per text character and every failure-link step lowers it, the same amortised argument as KMP, so scanning is O(text length) plus the number of reported matches (a text of all as with patterns a, aa, aaa, ... reports many matches per position, and no algorithm can report them faster than it writes them). The build is O(total length of the patterns) with Map transitions, plus the cost of copying the output lists (a "dictionary link" per node instead of a copied list avoids that). For a fixed small alphabet you can also precompute the full transition table so scanning never loops at all.

Suffix arrays: every suffix, in sorted order

The suffix array of a string is the list of the starting positions of all its suffixes, ordered by the suffixes' alphabetical order. For "banana" the suffixes in order are a, ana, anana, banana, na, nana, so the suffix array is [5, 3, 1, 0, 4, 2]. Once you have it, many questions about all substrings reduce to questions about neighbours in a sorted list, because every substring is a prefix of some suffix and substrings that start alike sit next to each other.

Building it. Sorting the suffixes as full strings is O(n² log n) in the worst case. Prefix doubling avoids comparing long strings: rank the suffixes by their first character, then repeatedly rank them by their first 2, 4, 8, ... characters. To order by the first 2k characters, compare the pair (rank by the first k characters of the suffix, rank by the first k characters of the suffix that starts k later). After about log₂ n rounds all ranks are distinct.

// O(n log² n) time (about log n rounds of a comparison sort), O(n) space
function suffixArray(s) {
  const n = s.length;
  if (n === 0) return [];
  const sa = Array.from({ length: n }, (_, i) => i);
  let rank = Array.from(s, (c) => c.charCodeAt(0)); // round 0: rank by the first character

  for (let k = 1; ; k *= 2) {
    const second = (i) => (i + k < n ? rank[i + k] : -1); // a suffix shorter than k sorts first
    sa.sort((a, b) => rank[a] - rank[b] || second(a) - second(b));

    const next = new Array(n).fill(0);
    for (let i = 1; i < n; i++) {
      const same = rank[sa[i - 1]] === rank[sa[i]] && second(sa[i - 1]) === second(sa[i]);
      next[sa[i]] = next[sa[i - 1]] + (same ? 0 : 1);
    }
    rank = next;
    if (rank[sa[n - 1]] === n - 1) return sa; // every suffix has its own rank: done
  }
}

The array alone is not enough for most problems; you usually want the LCP array too: lcp[i] is the length of the longest common prefix of the neighbouring suffixes sa[i] and sa[i + 1]. Computing it naively is quadratic, but Kasai's algorithm uses one fact: when you move from suffix i to suffix i + 1, the common prefix with its sorted neighbour can shrink by at most one, so you never need to restart the count from zero.

// O(n) time, O(n) space; lcp[r] is the common prefix of suffixes sa[r] and sa[r + 1]
function lcpArray(s, sa) {
  const n = s.length;
  const rank = new Array(n);
  for (let i = 0; i < n; i++) rank[sa[i]] = i;

  const lcp = new Array(Math.max(n - 1, 0)).fill(0);
  let h = 0; // the current common-prefix length, carried from one suffix to the next
  for (let i = 0; i < n; i++) {
    if (rank[i] === n - 1) { h = 0; continue; } // the last suffix has no right neighbour
    const j = sa[rank[i] + 1];
    while (i + h < n && j + h < n && s[i + h] === s[j + h]) h++;
    lcp[rank[i]] = h;
    if (h > 0) h--; // the next suffix shares at least h - 1 characters with its neighbour
  }
  return lcp;
}

// the number of different substrings: all n(n+1)/2, minus those counted twice
function countDistinctSubstrings(s) {
  const lcp = lcpArray(s, suffixArray(s));
  return (s.length * (s.length + 1)) / 2 - lcp.reduce((total, value) => total + value, 0);
}

// the longest substring that occurs at least twice (overlaps allowed)
function longestRepeatedSubstring(s) {
  const sa = suffixArray(s);
  const lcp = lcpArray(s, sa);
  let best = 0, at = 0;
  for (let i = 0; i < lcp.length; i++) {
    if (lcp[i] > best) { best = lcp[i]; at = sa[i]; }
  }
  return s.slice(at, at + best);
}

Dry run: s = "banana"

There are 6 · 7 / 2 = 21 substrings counted with repeats, and the LCP values add up to 1 + 3 + 0 + 0 + 2 = 6, so there are 21 − 6 = 15 distinct substrings. The largest LCP is 3, between "ana" and "anana", so the longest repeated substring is the first 3 characters of the suffix at position 3, which is "ana". Why the distinct count works: walking the sorted suffixes, each new suffix contributes only the prefixes that are longer than what it shares with the previous one, which is its length minus the LCP.

Linear-time constructions exist, but you will not be asked to write one in an interview. What you should be able to say: the suffix array plus the LCP array turns "distinct substrings", "longest repeated substring" and "does pattern P occur" (binary search the suffix array, O(m log n)) into short loops, at the price of O(n log² n) to build. For one-off questions about a single substring length, hashing with binary search is usually less code; the suffix array pays off when you ask many different questions about the same string.

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
• "Longest substring that appears twice / satisfies something monotone in the length," or many "are these two substrings equal" checks → prefix hashes plus binary search on the length, with two moduli, a random base and a verification on hits
• A dictionary of many words searched in one text, or "censor / tag every keyword" → Aho-Corasick: a trie with failure links, one pass over the text
• "Sum of the longest common prefixes with the whole string" → the sum of the Z array. "Is B a rotation of A" → B occurs in A + A. "Smallest or canonical rotation" → the two-pointer minimal rotation
• "Number of distinct substrings," "longest repeated substring," "k-th smallest substring" → a suffix array and its LCP array, rather than a new algorithm per question