On this page

String Algorithms (Module 7 Overview)

String processing is everywhere — search engines, compilers, bioinformatics, text editors, log parsers, URL routers. Yet string algorithms are often neglected in interview prep because they feel "niche." They are not. Pattern matching, edit distance, and trie-based search appear regularly in interviews at top companies, and understanding them deeply separates strong candidates from average ones.

This page is the overview lesson of Module 7 — String Algorithms in DSA: Zero to Mastery, and it is also the module's landing page. It does three jobs. First, it shows why the obvious way to search text is slow, on an example small enough to trace by hand, because every algorithm in this module is an answer to that slowness. Second, it gives you a map: which algorithm solves which problem, as a decision table and a diagram that links every lesson. Third, it gives a first, working look at the classic algorithms (KMP, Rabin–Karp, tries, suffix arrays, Manacher's algorithm and edit distance), each with a pointer to the lesson that goes deeper.

What problem are we solving?

Almost every lesson in this module answers some version of one question: where does this piece of text appear inside that bigger piece of text? Your editor's Ctrl+F asks it about one word in one file. A virus scanner asks it about a hundred thousand signatures in every file on your disk. A genome lab asks it about millions of short DNA reads against a reference three billion letters long. A search engine asks the reverse: which of a billion documents contain this word?

Two words appear constantly, so let us fix them now:

  • The text is the long string we search in. Its length is .
  • The pattern is the short string we search for. Its length is , and usually .

An occurrence (or match) of in is a position such that , that is, the letters of starting at are exactly the letters of . The position is also called a shift, because you can picture sliding the pattern places to the right along the text.

An everyday analogy: you have a strip of paper with the pattern written on it, and a long line of text on the table. You lay the strip under the text at the very left and check whether the letters line up. Then you slide the strip one letter to the right and check again, and again, until the strip falls off the end. That is the naive algorithm, and it is the right place to start.

How this module is organised

Module 7 has one overview (this page), ten deep lessons and a capstone. The order is deliberate. Hashing comes first because it is the most flexible tool and the easiest to code. KMP and Z come next: two ways to make single-pattern matching linear without probability, by reusing what was already matched. Aho–Corasick extends KMP's idea to many patterns at once. The suffix structures (array, automaton, tree) flip the problem around: preprocess the text once so that any later question about its substrings is fast. Palindromes and rotations are specialised structure in strings. Regex engines close the module by matching patterns with choices and repetition, not just fixed strings.

#LessonWhat you will be able to doMinutes
1String Algorithms (Overview)Explain why naive matching is , pick the right algorithm for a string problem, and run KMP, Rabin–Karp and a trie by hand.50
2String Hashing in DepthCompare any two substrings in , run Rabin–Karp, size the modulus with the birthday bound, and defend against anti-hash tests.55
3KMP & the Prefix FunctionBuild the prefix function by hand, match in with an amortised proof, and find periods and borders.55
4The Z-AlgorithmCompute the Z-array with the window, match with P + '$' + T, and convert between Z and the prefix function.45
5Aho–Corasick (Multi-Pattern Matching)Build a trie with failure and output links and find every occurrence of many patterns in one pass.55
6Suffix Arrays & LCPBuild a suffix array in , compute LCP with Kasai, and answer repeated-substring questions.60
7Suffix AutomatonBuild the smallest automaton of all substrings in and count distinct substrings and occurrences.60
8Suffix Trees (Ukkonen Intuition)Explain the compressed suffix trie, the idea behind Ukkonen's online construction, and when a tree beats an array.50
9Palindromes & Manacher's AlgorithmFind all maximal palindromes in and build a palindromic tree (eertree).50
10Minimal Rotation, Lyndon Words & Booth's AlgorithmFind the lexicographically smallest rotation in and factor a string into Lyndon words.40
11How Regex Engines WorkCompile a regex to an NFA, simulate it in linear time, and explain catastrophic backtracking.50
—CapstoneCombine the module's tools into a working text-search project and measure it.180

Lesson time totals about 570 minutes, a little under ten hours, plus three hours for the capstone and about as much again for the practice ladders.

The map of the module

Arrows mean "read this first". The lessons fall into three big ideas: reuse what you matched (KMP, Z, Aho–Corasick), fingerprint substrings (hashing), and preprocess the text (suffix structures).

flowchart TD
    M1["Module 1: Strings in Depth"] --> OV["1 · String Algorithms overview"]
    TR["Module 3: Tries"] --> AC
    OV --> SH["2 · String Hashing"]
    OV --> KMP["3 · KMP & Prefix Function"]
    KMP --> Z["4 · Z-Algorithm"]
    KMP --> AC["5 · Aho-Corasick"]
    SH --> SA["6 · Suffix Arrays & LCP"]
    Z --> SA
    SA --> SAM["7 · Suffix Automaton"]
    SA --> ST["8 · Suffix Trees"]
    SAM --> ST
    Z --> PAL["9 · Palindromes & Manacher"]
    SH --> PAL
    KMP --> ROT["10 · Minimal Rotation & Lyndon"]
    AC --> RX["11 · Regex Engines"]
    RX --> CAP["Capstone"]
    ST --> CAP
    PAL --> CAP
    ROT --> CAP
    DP["Module 6: String DP"] -.-> CAP

The dotted edge is a related module rather than a prerequisite: edit distance and LCS live in the dynamic programming series, and the capstone uses them for fuzzy matching.

Which algorithm for which problem?

Start from the question you are asked, not from the algorithm you know. The first column is how the problem usually sounds.

The problem asks…UseTimeLesson
Find one pattern in one text, onceLibrary find; for a guarantee, KMP or ZKMP, Z
Find one pattern in a stream you cannot re-readKMP (or its automaton) amortised per characterKMP
Find many patterns in one text in one passAho–CorasickAho–Corasick
Many patterns, all of the same lengthRabin–Karp with a set of hashes expectedHashing
Compare many substrings for equalityPrefix hashes per comparison after Hashing
Longest prefix that is also a suffix; period of a stringPrefix function or Z-arrayKMP, Z
For each position, how far the string matches its own startZ-arrayZ
Text is fixed, many pattern queries arrive laterSuffix array ( per query) or suffix automaton () or buildSuffix Arrays, Suffix Automaton
Longest repeated substring; number of distinct substringsSuffix array + LCP (or hashing + binary search)Suffix Arrays
Longest common substring of two stringsSuffix automaton of one, walk the otherSuffix Automaton
Many substring questions on one text, online, with full generalitySuffix tree buildSuffix Trees
Longest palindromic substring; all palindromesManacher; eertree for distinct palindromesManacher
Smallest rotation; canonical form of a cyclic stringBooth's algorithm or Duval's Lyndon factorizationMinimal Rotation
Patterns with *, ?, alternatives, character classesNFA simulation (Thompson) or a DFA or after buildingRegex Engines
Prefix lookups, autocomplete, "starts with"Trie per wordTries
"Closest" string, typos, editsEdit-distance DPString DP

The same map as a decision flow, for when you are staring at a problem statement:

flowchart TD
    Q["String problem"] --> F{"Exact fixed patterns?"}
    F -->|"no: wildcards, choices, repetition"| RX["Regex engine: NFA or DFA"]
    F -->|"no: typos, edits"| ED["Edit-distance DP"]
    F -->|yes| K{"How many patterns?"}
    K -->|one| ONE{"Need a worst-case guarantee?"}
    ONE -->|yes| KZ["KMP or Z"]
    ONE -->|"no, want short code"| RK["Rabin-Karp"]
    K -->|many| SAME{"Text fixed, queries later?"}
    SAME -->|"no, scan once"| AC["Aho-Corasick"]
    SAME -->|yes| SUF["Suffix array or automaton"]
    Q --> S{"About the string's own structure?"}
    S -->|"repeats, distinct substrings"| SUF
    S -->|"periods, borders"| KZ
    S -->|palindromes| MAN["Manacher or eertree"]
    S -->|rotations| BOOTH["Booth or Lyndon"]

Pattern triggers

If the problem says or has…Think of…
"find all occurrences of in "KMP, Z, or Rabin–Karp
"any of these words", "a dictionary of banned terms", "signatures"Aho–Corasick
"is substring equal to substring ", asked many timesPrefix hashes
"longest prefix which is also a suffix", "smallest period", "repeated times"Prefix function
"for every position, the longest match with the prefix"Z-array
"longest repeated substring", "-th smallest substring", "number of distinct substrings"Suffix array + LCP, or suffix automaton
"longest palindromic substring" with up to Manacher
"lexicographically smallest rotation", "necklace"Booth / Lyndon
"words starting with", "autocomplete"Trie
"minimum edits", "similar strings"Edit-distance DP
Patterns contain . * ``

Why Naive Matching Fails

The brute-force approach to finding pattern of length in text of length checks every position:

For large inputs, this is unacceptable. Consider searching a 1GB log file for a 100-character pattern — naive matching could take billions of comparisons. The algorithms in this section reduce this to or .

The naive algorithm, in words

Try every shift . At each shift, compare with , with , and so on. Stop at the first mismatch, or report a match if all letters agree. Then move the pattern one place to the right and start comparing again from .

That last phrase is the whole problem. Whatever the algorithm learned about the text at shift is forgotten at shift .

def naive_search(text: str, pattern: str) -> tuple[list[int], int]:
    """All start indices of pattern in text, plus the number of character comparisons made."""
    n, m = len(text), len(pattern)
    found, comparisons = [], 0
    for s in range(n - m + 1):          # every possible alignment ("shift")
        j = 0
        while j < m:
            comparisons += 1
            if text[s + j] != pattern[j]:
                break                   # mismatch: give up on this shift
            j += 1
        if j == m:
            found.append(s)
    return found, comparisons


if __name__ == "__main__":
    assert naive_search("AAAAAB", "AAB") == ([3], 12)
    assert naive_search("ABABDABACDABABCABAB", "ABABCABAB")[0] == [10]
    assert naive_search("aaaa", "aa") == ([0, 1, 2], 6)
    assert naive_search("ab", "abc") == ([], 0)
    print("all tests passed")
import java.util.ArrayList;
import java.util.List;

public class Naive {
    /** Start indices of pattern in text; comparisons[0] receives the number of character comparisons. */
    static List<Integer> naiveSearch(String text, String pattern, long[] comparisons) {
        int n = text.length(), m = pattern.length();
        List<Integer> found = new ArrayList<>();
        for (int s = 0; s + m <= n; s++) {           // every possible alignment ("shift")
            int j = 0;
            while (j < m) {
                comparisons[0]++;
                if (text.charAt(s + j) != pattern.charAt(j)) break;   // mismatch: give up on this shift
                j++;
            }
            if (j == m) found.add(s);
        }
        return found;
    }

    public static void main(String[] args) {
        long[] c = {0};
        if (!naiveSearch("AAAAAB", "AAB", c).equals(List.of(3)) || c[0] != 12) throw new AssertionError("AAB");
        if (!naiveSearch("ABABDABACDABABCABAB", "ABABCABAB", new long[1]).equals(List.of(10))) throw new AssertionError("long");
        c[0] = 0;
        if (!naiveSearch("aaaa", "aa", c).equals(List.of(0, 1, 2)) || c[0] != 6) throw new AssertionError("aa");
        c[0] = 0;
        if (!naiveSearch("ab", "abc", c).isEmpty() || c[0] != 0) throw new AssertionError("short");
        System.out.println("all tests passed");
    }
}
#include <cassert>
#include <iostream>
#include <string>
#include <utility>
#include <vector>
using namespace std;

// All start indices of pattern in text, plus the number of character comparisons made.
pair<vector<int>, long long> naiveSearch(const string& text, const string& pattern) {
    size_t n = text.size(), m = pattern.size();
    vector<int> found;
    long long comparisons = 0;
    for (size_t s = 0; s + m <= n; s++) {          // every possible alignment ("shift")
        size_t j = 0;
        while (j < m) {
            comparisons++;
            if (text[s + j] != pattern[j]) break;  // mismatch: give up on this shift
            j++;
        }
        if (j == m) found.push_back((int)s);
    }
    return make_pair(found, comparisons);
}

int main() {
    pair<vector<int>, long long> r = naiveSearch("AAAAAB", "AAB");
    assert(r.first == vector<int>({3}) && r.second == 12);
    assert(naiveSearch("ABABDABACDABABCABAB", "ABABCABAB").first == vector<int>({10}));
    r = naiveSearch("aaaa", "aa");
    assert(r.first == vector<int>({0, 1, 2}) && r.second == 6);
    r = naiveSearch("ab", "abc");
    assert(r.first.empty() && r.second == 0);
    cout << "all tests passed\n";
}
/** All start indices of pattern in text, plus the number of character comparisons made. */
function naiveSearch(text: string, pattern: string): { found: number[]; comparisons: number } {
  const n = text.length;
  const m = pattern.length;
  const found: number[] = [];
  let comparisons = 0;
  for (let s = 0; s + m <= n; s++) { // every possible alignment ("shift")
    let j = 0;
    while (j < m) {
      comparisons++;
      if (text[s + j] !== pattern[j]) break; // mismatch: give up on this shift
      j++;
    }
    if (j === m) found.push(s);
  }
  return { found, comparisons };
}

const eq = (a: number[], b: number[]) => a.length === b.length && a.every((x, i) => x === b[i]);
let r = naiveSearch("AAAAAB", "AAB");
if (!eq(r.found, [3]) || r.comparisons !== 12) throw new Error("AAB");
if (!eq(naiveSearch("ABABDABACDABABCABAB", "ABABCABAB").found, [10])) throw new Error("long");
r = naiveSearch("aaaa", "aa");
if (!eq(r.found, [0, 1, 2]) || r.comparisons !== 6) throw new Error("aa");
r = naiveSearch("ab", "abc");
if (r.found.length !== 0 || r.comparisons !== 0) throw new Error("short");
console.log("all tests passed");

All four versions count comparisons so you can see the cost, and all four were compiled and run with the assertions shown.

Worked example: "AAB" in "AAAAAB"

Text $T = $ AAAAAB (), pattern $P = $ AAB (). There are shifts. Let us do it the way you would at a whiteboard.

Shift 0. Line AAB up under AAA. $T[0] = $ A matches $P[0] = $ A. $T[1] = $ A matches $P[1] = $ A. $T[2] = $ A does not match $P[2] = $ B. Three comparisons, no match.

Shift 1. Slide one place. Now we compare with — but we already know is A, we read it a moment ago. And with : we also already know is A. The algorithm re-reads both, then fails on $T[3] = $ A versus B. Three comparisons, no match.

Shift 2. The same story one place further: two re-reads, one fresh mismatch. Three comparisons.

Shift 3. $T[3..5] = $ AAB. All three agree. Three comparisons, match at 3.

Trace table

Each row is one character comparison.

StepShift Compare vs ResultAlready read before?Comparisons so far
100 = A vs Aequalno1
201 = A vs Aequalno2
302 = A vs Bmismatchno3
410 = A vs Aequalyes4
511 = A vs Aequalyes5
612 = A vs Bmismatchno6
720 = A vs Aequalyes7
821 = A vs Aequalyes8
922 = A vs Bmismatchno9
1030 = A vs Aequalyes10
1131 = A vs Aequalyes11
1232 = B vs Bequal → match at 3no12

Twelve comparisons for a six-letter text: exactly . Six of them (the "yes" rows) re-read a letter of the text that the algorithm had already read and already knew was A. Step through the same run below; the shaded block is the current alignment, green cells have matched at this shift, the amber cell is being compared, and the grey cell is a mismatch.

How slow is it, really?

Worst case. Text (all a's) and pattern . Every shift matches letters and fails on the last, so the cost is exactly . With and that is 9,990,100 comparisons (we ran it). For a 1 GB text and a 100-letter pattern it is about . Inputs like this are not exotic: long runs of the same byte appear in binary files, DNA (poly-A tails) and padded logs.

Best case. If the very first letter of never appears in , every shift fails after one comparison: comparisons.

Typical case. On random text over an alphabet of letters, a shift reaches its -th comparison only if the first letters matched, which happens with probability . So the expected comparisons per shift are . We measured this on a random 100,000-letter text and a random 20-letter pattern:

Alphabet size Measured comparisons per shiftBound
2 (binary)1.9952.000
4 (DNA)1.3321.333
26 (letters)1.0401.040

So on ordinary English text the naive scan is close to linear. That is why it is a perfectly good choice for one-off searches on normal input, and why real libraries start from it. The problem is the guarantee: an adversary, or simply unlucky data, can push it to .

What real libraries do

glibc's strstr and memmem use the Crochemore–Perrin Two-Way algorithm for longer needles, which is linear in the worst case with extra memory. CPython's str.find uses a Boyer–Moore–Horspool-style "fastsearch" and, since Python 3.10, switches to Two-Way for long needles, precisely to remove the worst case. GNU grep's kwset matcher uses Boyer–Moore for a single fixed string and a multi-keyword automaton (Commentz-Walter, Aho–Corasick's Boyer–Moore-flavoured cousin) for several. All of them are refinements of the ideas in this module.

What the naive algorithm throws away, and the three fixes

Look again at shift 1 in the trace. When shift 0 failed at , we had learned that $T[0..1] = $ AA. That is information about the text. Naive matching discards it and re-reads. The algorithms in this module are three different ways of not throwing information away:

  1. Reuse what you matched (KMP, Z, Aho–Corasick). When a mismatch happens after matching AA, the matched part is a copy of the pattern's own prefix. So which shifts are still possible depends only on the pattern, and can be computed in advance. KMP precomputes, for each prefix of , "how much of what I matched can I keep". The text pointer never moves backwards: in the worst case. Z does the same with a different table; Aho–Corasick does it for many patterns at once.
  2. Fingerprint substrings (hashing, Rabin–Karp). Instead of comparing letters per shift, compare one number: a hash of the window, updated in as the window slides. Expected , ten lines of code, and the same trick compares any two substrings in .
  3. Preprocess the text (suffix array, automaton, tree). If the text is fixed and the patterns arrive later (a genome, a code base, a document collection), build an index of all its suffixes once. Then each pattern query costs about or , independent of .
ApproachPreprocessSearchWorst caseExtra memoryGood for
Naivenone worst, ~ typicalshort patterns, normal text, one-off
Rabin–Karp expectedshort code, many same-length patterns
KMP / Zguarantees, streams
Aho–Corasicklinear or lessmany patterns
Suffix array on the text per pattern—fixed text, many queries
Suffix automaton on the text per pattern—fixed text, substring statistics

KMP (Knuth-Morris-Pratt)

KMP achieves pattern matching by precomputing a failure function (also called the prefix function or partial match table). When a mismatch occurs, instead of restarting from the next position, KMP uses the failure function to skip characters that are guaranteed to match.

The Failure Function

The failure function gives the length of the longest proper prefix of that is also a suffix.

Example: Pattern = "ABABAC"

Longest proper prefix = suffix
0A(none)0
1AB(none)0
2ABAA1
3ABABAB2
4ABABAABA3
5ABABAC(none)0
graph LR
    subgraph "KMP Failure Function for ABABAC"
        P0["A<br/>π=0"] --> P1["B<br/>π=0"]
        P1 --> P2["A<br/>π=1"]
        P2 --> P3["B<br/>π=2"]
        P3 --> P4["A<br/>π=3"]
        P4 --> P5["C<br/>π=0"]
    end

Building the Failure Function

TypeScript:

function buildFailure(pattern: string): number[] {
  const m = pattern.length;
  const pi = new Array(m).fill(0);
  let len = 0; // length of previous longest prefix suffix
  let i = 1;

  while (i < m) {
    if (pattern[i] === pattern[len]) {
      len++;
      pi[i] = len;
      i++;
    } else if (len > 0) {
      len = pi[len - 1]; // fall back — do NOT increment i
    } else {
      pi[i] = 0;
      i++;
    }
  }

  return pi;
}

Python:

def build_failure(pattern: str) -> list[int]:
    m = len(pattern)
    pi = [0] * m
    length = 0  # length of previous longest prefix suffix
    i = 1

    while i < m:
        if pattern[i] == pattern[length]:
            length += 1
            pi[i] = length
            i += 1
        elif length > 0:
            length = pi[length - 1]  # fall back
        else:
            pi[i] = 0
            i += 1

    return pi

TypeScript:

function kmpSearch(text: string, pattern: string): number[] {
  const n = text.length;
  const m = pattern.length;
  const pi = buildFailure(pattern);
  const matches: number[] = [];

  let j = 0; // index in pattern

  for (let i = 0; i < n; i++) {
    while (j > 0 && text[i] !== pattern[j]) {
      j = pi[j - 1]; // fall back using failure function
    }

    if (text[i] === pattern[j]) {
      j++;
    }

    if (j === m) {
      matches.push(i - m + 1); // match found at index i - m + 1
      j = pi[j - 1]; // continue searching
    }
  }

  return matches;
}

// Example
console.log(kmpSearch("ABABDABACDABABCABAB", "ABABCABAB"));
// Output: [10]

Correction (2026-11-11)

An earlier version of this page gave the output of this example as [9]. The pattern ABABCABAB starts at index 10 of ABABDABACDABABCABAB (indices 10–18); [10] was confirmed by running the code in Python, TypeScript and the four-language versions in the KMP lesson.

Python:

def kmp_search(text: str, pattern: str) -> list[int]:
    n, m = len(text), len(pattern)
    pi = build_failure(pattern)
    matches = []
    j = 0

    for i in range(n):
        while j > 0 and text[i] != pattern[j]:
            j = pi[j - 1]

        if text[i] == pattern[j]:
            j += 1

        if j == m:
            matches.append(i - m + 1)
            j = pi[j - 1]

    return matches
MetricValue
Preprocessing
Searching
Total
Space for failure function

TIP

KMP is the go-to algorithm when you need guaranteed matching. It never backtracks on the text — each character is examined at most twice. This makes it ideal for streaming data where you cannot re-read input.

Go deeper: KMP & the Prefix Function builds the failure function by hand on ababcabab, proves the bound with an amortised argument, and uses it for periods, prefix counts and the KMP automaton. The Z-Algorithm computes an equivalent table with a different, often easier, loop.

Rabin-Karp (Rolling Hash)

Rabin-Karp uses hashing to find pattern matches. Compute a hash of the pattern and a rolling hash of each window in the text. Only perform character-by-character comparison when hashes match.

Rolling Hash

A polynomial rolling hash for a string with base and modulus :

When sliding the window right by one character, update in :

TypeScript:

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

  const BASE = 256;
  const MOD = 1_000_000_007;
  const matches: number[] = [];

  // Compute BASE^(m-1) mod MOD
  let basePow = 1;
  for (let i = 0; i < m - 1; i++) {
    basePow = (basePow * BASE) % MOD;
  }

  // Compute initial hashes
  let patternHash = 0;
  let windowHash = 0;

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

  for (let i = 0; i <= n - m; i++) {
    if (windowHash === patternHash) {
      // Verify character by character (avoid hash collision false positive)
      if (text.substring(i, i + m) === pattern) {
        matches.push(i);
      }
    }

    // Roll the hash forward
    if (i < n - m) {
      windowHash = (
        (windowHash - text.charCodeAt(i) * basePow % MOD + MOD) * BASE
        + text.charCodeAt(i + m)
      ) % MOD;
    }
  }

  return matches;
}

Python:

def rabin_karp(text: str, pattern: str) -> list[int]:
    n, m = len(text), len(pattern)
    if m > n:
        return []

    BASE = 256
    MOD = 10**9 + 7
    matches = []

    base_pow = pow(BASE, m - 1, MOD)

    pattern_hash = 0
    window_hash = 0

    for i in range(m):
        pattern_hash = (pattern_hash * BASE + ord(pattern[i])) % MOD
        window_hash = (window_hash * BASE + ord(text[i])) % MOD

    for i in range(n - m + 1):
        if window_hash == pattern_hash:
            if text[i:i + m] == pattern:
                matches.append(i)

        if i < n - m:
            window_hash = (
                (window_hash - ord(text[i]) * base_pow % MOD + MOD) * BASE
                + ord(text[i + m])
            ) % MOD

    return matches
MetricValue
Average case
Worst case (many hash collisions)
Space extra

WARNING

Rabin-Karp's worst case is due to hash collisions. Use a good modulus (large prime) and verify matches. For guaranteed , use KMP. Rabin-Karp's advantage is its simplicity and its ability to search for multiple patterns simultaneously.

Two clarifications (2026-11-11). First, the worst case is not only about collisions: every real match is verified letter by letter, so on text aaaa…a with pattern aa…a all windows match and verification alone costs . Second, "multiple patterns simultaneously" works directly when the patterns share one length (put their hashes in a set); patterns of many lengths need one rolling hash per length, or Aho–Corasick. The fixed BASE = 256 above is fine for ordinary input but can be attacked when an adversary chooses the input; choose the base at random.

Go deeper: String Hashing in Depth builds the hash from "turn a word into a number", steps through Rabin–Karp's sliding window in a visualizer, computes collision probabilities with the birthday bound, and covers double hashing and anti-hash tests.

Trie (Prefix Tree)

A trie stores strings by sharing common prefixes. Each node represents a character, and paths from root to marked nodes spell out stored strings.

graph TD
    ROOT["(root)"] --> A["a"]
    ROOT --> T["t"]
    A --> AP["p"] --> APP["p"] --> APPL["l"] --> APPLE["e ✓"]
    AP --> APE["e ✓"]
    T --> TO["o ✓"]
    T --> TE["e"] --> TEA["a ✓"]
    TE --> TEN["n ✓"]

Trie storing: "apple", "ape", "to", "tea", "ten"

Implementation

TypeScript:

class TrieNode {
  children: Map<string, TrieNode> = new Map();
  isEnd = false;
  word = ""; // store the complete word at leaf nodes
}

class Trie {
  root = new TrieNode();

  insert(word: string): void {
    let node = this.root;
    for (const ch of word) {
      if (!node.children.has(ch)) {
        node.children.set(ch, new TrieNode());
      }
      node = node.children.get(ch)!;
    }
    node.isEnd = true;
    node.word = word;
  }

  search(word: string): boolean {
    const node = this._findNode(word);
    return node !== null && node.isEnd;
  }

  startsWith(prefix: string): boolean {
    return this._findNode(prefix) !== null;
  }

  autocomplete(prefix: string, limit = 10): string[] {
    const node = this._findNode(prefix);
    if (!node) return [];

    const results: string[] = [];
    this._dfs(node, results, limit);
    return results;
  }

  private _findNode(s: string): TrieNode | null {
    let node = this.root;
    for (const ch of s) {
      if (!node.children.has(ch)) return null;
      node = node.children.get(ch)!;
    }
    return node;
  }

  private _dfs(node: TrieNode, results: string[], limit: number): void {
    if (results.length >= limit) return;
    if (node.isEnd) results.push(node.word);

    for (const [, child] of node.children) {
      this._dfs(child, results, limit);
    }
  }
}

Python:

class TrieNode:
    def __init__(self):
        self.children: dict[str, 'TrieNode'] = {}
        self.is_end = False
        self.word = ""

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        node = self.root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.is_end = True
        node.word = word

    def search(self, word: str) -> bool:
        node = self._find_node(word)
        return node is not None and node.is_end

    def starts_with(self, prefix: str) -> bool:
        return self._find_node(prefix) is not None

    def autocomplete(self, prefix: str, limit: int = 10) -> list[str]:
        node = self._find_node(prefix)
        if not node:
            return []
        results: list[str] = []
        self._dfs(node, results, limit)
        return results

    def _find_node(self, s: str) -> TrieNode | None:
        node = self.root
        for ch in s:
            if ch not in node.children:
                return None
            node = node.children[ch]
        return node

    def _dfs(self, node: TrieNode, results: list[str], limit: int) -> None:
        if len(results) >= limit:
            return
        if node.is_end:
            results.append(node.word)
        for child in node.children.values():
            self._dfs(child, results, limit)
OperationTime Complexity
Insert where = word length
Search
Prefix search
Autocomplete where = results
Space where = alphabet size

Go deeper: Tries (Module 3) covers array versus map children, deletion, compressed (radix) tries and XOR tries. Aho–Corasick turns a trie of patterns into an automaton that finds all of them in one pass over a text.

Suffix Arrays

A suffix array is a sorted array of all suffixes of a string. It is a space-efficient alternative to suffix trees and powers many advanced string operations.

For string "banana":

IndexSuffixSorted Position
0banana3
1anana2
2nana5
3ana1
4na4
5a0

Sorted suffix array: [5, 3, 1, 0, 4, 2] corresponding to a, ana, anana, banana, na, nana.

Correction (2026-11-11)

The "Sorted Position" column previously repeated the suffix array itself (5, 3, 1, 0, 4, 2) instead of each suffix's position in sorted order. The corrected column is the rank array (the inverse of the suffix array): banana is the 4th smallest suffix (position 3, counting from 0), a the smallest (position 0). Checked by sorting the suffixes in code.

Python (simple construction):

def build_suffix_array(s: str) -> list[int]:
    """Naive construction: sort the suffixes themselves. O(n^2 log n) worst case."""
    n = len(s)
    suffixes = [(s[i:], i) for i in range(n)]
    suffixes.sort()
    return [idx for _, idx in suffixes]

Correction (2026-11-11): the docstring previously said "". Sorting suffixes makes comparisons, and each comparison of two suffixes can cost , so this version is in the worst case (and builds characters of slices), as the tip below says. is the prefix-doubling method with a comparison sort, covered in the Suffix Arrays lesson.

TIP

The naive suffix array construction is . The DC3/SA-IS algorithm builds it in . For interviews, the naive approach is usually sufficient — know that construction exists.

Go deeper: Suffix Arrays & LCP builds the array in by prefix doubling and the LCP array with Kasai's algorithm; Suffix Automaton and Suffix Trees are the two other ways to index every substring of a text.

Manacher's Algorithm (Longest Palindromic Substring)

Manacher's algorithm finds the longest palindromic substring in . It exploits the symmetry of palindromes to avoid redundant comparisons.

Key Insight

If we know the palindrome centered at position extends to radius and we are computing the palindrome at position , then 's mirror position may already be computed. We can reuse that information.

graph LR
    subgraph "Palindrome Mirroring"
        direction LR
        L["Left<br/>boundary"] ~~~ JP["j' (mirror)"] ~~~ C["Center i"] ~~~ J["j (current)"] ~~~ R["Right<br/>boundary"]
    end

TypeScript:

function longestPalindrome(s: string): string {
  // Transform: "abc" → "^#a#b#c#$"
  const t = `^#${s.split("").join("#")}#$`;
  const n = t.length;
  const p = new Array(n).fill(0);

  let center = 0, right = 0;

  for (let i = 1; i < n - 1; i++) {
    const mirror = 2 * center - i;

    if (i < right) {
      p[i] = Math.min(right - i, p[mirror]);
    }

    // Expand around center
    while (t[i + p[i] + 1] === t[i - p[i] - 1]) {
      p[i]++;
    }

    // Update center and right boundary
    if (i + p[i] > right) {
      center = i;
      right = i + p[i];
    }
  }

  // Find max
  let maxLen = 0, maxCenter = 0;
  for (let i = 1; i < n - 1; i++) {
    if (p[i] > maxLen) {
      maxLen = p[i];
      maxCenter = i;
    }
  }

  const start = (maxCenter - maxLen) / 2;
  return s.substring(start, start + maxLen);
}

Python:

def longest_palindrome(s: str) -> str:
    # Transform: "abc" → "^#a#b#c#$"
    t = f"^#{'#'.join(s)}#$"
    n = len(t)
    p = [0] * n
    center = right = 0

    for i in range(1, n - 1):
        mirror = 2 * center - i

        if i < right:
            p[i] = min(right - i, p[mirror])

        while t[i + p[i] + 1] == t[i - p[i] - 1]:
            p[i] += 1

        if i + p[i] > right:
            center = i
            right = i + p[i]

    max_len = max(p)
    max_center = p.index(max_len)
    start = (max_center - max_len) // 2
    return s[start:start + max_len]
MetricValue
Time
Space

Go deeper: Palindromes & Manacher's Algorithm proves why the right boundary only moves forward (hence ), handles odd and even centres without the # transform, and builds the palindromic tree (eertree).

Edit Distance (Levenshtein)

The edit distance between two strings is the minimum number of single-character operations (insert, delete, replace) to transform one into the other.

The three operations:

  • : delete from
  • : insert into
  • : replace in

TypeScript:

function editDistance(s1: string, s2: string): number {
  const m = s1.length;
  const n = s2.length;
  const dp: number[][] = Array.from(
    { length: m + 1 },
    (_, i) => {
      const row = new Array(n + 1).fill(0);
      row[0] = i;
      return row;
    }
  );

  for (let j = 0; j <= n; j++) dp[0][j] = j;

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (s1[i - 1] === s2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1];
      } else {
        dp[i][j] = 1 + Math.min(
          dp[i - 1][j],     // delete
          dp[i][j - 1],     // insert
          dp[i - 1][j - 1]  // replace
        );
      }
    }
  }

  return dp[m][n];
}

Python:

def edit_distance(s1: str, s2: str) -> int:
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(m + 1):
        dp[i][0] = i
    for j in range(n + 1):
        dp[0][j] = j

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i - 1] == s2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = 1 + min(
                    dp[i - 1][j],      # delete
                    dp[i][j - 1],      # insert
                    dp[i - 1][j - 1]   # replace
                )

    return dp[m][n]

Complexity: time, space (reducible to with space optimization).

TIP

Edit distance is used everywhere: spell checkers, DNA sequence alignment, fuzzy search, diff utilities. In interviews, it's the canonical 2D DP problem. Make sure you can derive the recurrence from scratch.

Go deeper: String DP in the dynamic programming series fills the edit-distance and LCS tables cell by cell, recovers the actual edits, and reduces memory to two rows.

Algorithm Comparison

AlgorithmProblemTimeSpaceKey Idea
NaiveExact matching worst, near on random textTry every shift
KMPExact matchingFailure function
Z-algorithmExact matching, prefix matches window reuse
Rabin-KarpExact matching avgRolling hash
Aho–CorasickMany patterns at onceTrie + failure links
TriePrefix searchShared prefixes
Suffix ArrayMany string ops buildSorted suffixes
Suffix AutomatonSubstring statistics buildEquivalence classes of end positions
Manacher'sLongest palindromeMirror symmetry
Edit DistanceString similarity2D DP

Common mistakes & interview follow-ups

"Why not just use the built-in find?" For one search on ordinary text, do. Know its worst case: a naive or Horspool-style search can be on inputs like aaaa…ab, while glibc and CPython 3.10+ switch to the linear Two-Way algorithm for long needles. In an interview, say so, then implement KMP or Z if asked for a guarantee.

"KMP or Z?" Equivalent power for single-pattern matching. Z is easier to get right from memory (P + sep + T, then look for values ); KMP's prefix function streams over the text without storing it and extends to Aho–Corasick and automata.

"Is Rabin–Karp exact?" Only if you verify candidate matches; then the output is always right and only the time is random. Without verification it is a Monte Carlo algorithm with a small error probability you should be able to quantify.

"How do you search for 10,000 words at once?" Aho–Corasick, . Running KMP 10,000 times costs .

"The text is fixed and queries keep coming." Index the text: suffix array (binary search, per query), suffix automaton () or an FM-index for compressed search over huge texts.

Mistakes interviewers watch for: restarting the text pointer after a mismatch (that is the naive algorithm again); if instead of while in the KMP fallback; forgetting overlapping matches ("aa" in "aaaa" occurs 3 times); off-by-one at the last shift ( runs to inclusive); empty pattern; and in hashing, negative remainders and 64-bit overflow.

How to study this module

  1. Read this overview and trace the naive search, KMP and Rabin–Karp sections by hand.
  2. Do lessons 2–4 in order. Hashing first gives you a fast brute-force oracle for testing KMP and Z: compare their outputs on thousands of random strings over the alphabet {a, b}, where bugs show up fastest.
  3. Lesson 5 (Aho–Corasick) needs KMP's failure-link idea and the Tries lesson.
  4. Lessons 6–8 are the heaviest. Do suffix arrays first; the automaton and the tree are easier once "all suffixes, sorted" is familiar.
  5. Lessons 9–11 can be read in any order after lesson 4.
  6. For every problem in the practice ladders, write the brute force first and keep it as a checker.

Further Reading

  • Arrays & Strings — foundational string manipulation patterns
  • Dynamic Programming — edit distance and LCS are core DP problems
  • Hash Tables — hashing fundamentals used in Rabin-Karp
  • Advanced Data Structures — segment trees for range queries on strings
  • Bit Manipulation — bitwise tricks in rolling hashes
  • Strings in Depth — encodings, immutability and the string operations every language gives you
  • Tries — the prefix tree in depth
  • Regex Mastery — using regular expressions well, before How Regex Engines Work explains how they run
  • Dan Gusfield, Algorithms on Strings, Trees, and Sequences, Cambridge University Press, 1997 — the standard reference for this whole module.
  • Maxime Crochemore, Christophe Hancart, Thierry Lecroq, Algorithms on Strings, Cambridge University Press, 2007.
  • Thomas H. Cormen et al., Introduction to Algorithms, 4th ed., Chapter 32 "String Matching" (naive, Rabin–Karp, finite automata, KMP, suffix arrays).
  • Maxime Crochemore and Dominique Perrin, "Two-way string-matching", Journal of the ACM 38(3), 1991 — the algorithm behind glibc's strstr.
  • cp-algorithms, String Processing section: prefix function, Z-function, hashing, Aho–Corasick, suffix array and automaton.

Try It Yourself

Problem 1: Use the KMP algorithm to find all occurrences of pattern "ABA" in text "ABABABA". First, build the failure function.

Solution

Failure function for "ABA":

  • pi[0] = 0 (A: no proper prefix = suffix)
  • pi[1] = 0 (AB: no match)
  • pi[2] = 1 (ABA: "A" is both prefix and suffix)

KMP search on "ABABABA":

  • i=0: A matches A, j=1
  • i=1: B matches B, j=2
  • i=2: A matches A, j=3 → match at index 0. j = pi[2] = 1
  • i=3: B matches B, j=2
  • i=4: A matches A, j=3 → match at index 2. j = pi[2] = 1
  • i=5: B matches B, j=2
  • i=6: A matches A, j=3 → match at index 4. j = pi[2] = 1

Answer: Matches at indices [0, 2, 4].

Problem 2: Insert the words "app", "apple", "ape", "apply" into a Trie. How many nodes does the Trie have (excluding root)?

Solution

Build the trie character by character:

  • "app": root → a → p → p (3 nodes)
  • "apple": root → a → p → p → l → e (2 new nodes: l, e)
  • "ape": root → a → p → e (1 new node: e after the first p)
  • "apply": root → a → p → p → l → y (1 new node: y)

Total nodes excluding root: 7 (a, p, p, l, e, e, y)

Problem 3: Find the longest palindromic substring in "babad".

Solution

Expand from each center (including between-character centers):

  • Center at index 0 (b): "b" (length 1)
  • Center at index 1 (a): "a" (1), expand: "bab" (3)
  • Center at index 2 (b): "b" (1), expand: "aba" (3)
  • Center at index 3 (a): "a" (1)
  • Center at index 4 (d): "d" (1)
  • Between-character centers: no even-length palindromes longer than 0.

Answer: "bab" or "aba" (both length 3).

Problem 4: Compute the edit distance between "horse" and "ros".

Solution

Build the DP table:

    ""  r  o  s
""   0  1  2  3
h    1  1  2  3
o    2  2  1  2
r    3  2  2  2
s    4  3  3  2
e    5  4  4  3
  • horse → rorse (replace h with r)
  • rorse → rose (remove r at position 2)
  • rose → ros (remove e) Answer: 3 operations.

Problem 5: Given the suffix array concept, list all suffixes of "abac" in sorted order.

Solution

All suffixes:

  • Index 0: "abac"
  • Index 1: "bac"
  • Index 2: "ac"
  • Index 3: "c"

Sorted alphabetically: "abac", "ac", "bac", "c" Suffix array: [0, 2, 1, 3]

Quick Quiz

1. What is the time complexity of the KMP pattern matching algorithm?

  • a)
  • b)
  • c)
  • d)
Answer

b) — KMP preprocesses the pattern in to build the failure function, then scans the text in . It never backtracks on the text.

2. What is the key advantage of Rabin-Karp over KMP?

  • a) Guaranteed worst case
  • b) Lower memory usage
  • c) Ability to search for multiple patterns simultaneously
  • d) Better cache performance
Answer

c) Ability to search for multiple patterns simultaneously — Rabin-Karp can compute rolling hashes for multiple patterns at once, checking all of them against each window hash. KMP requires a separate failure function per pattern.

3. What is the space complexity of a Trie storing words of average length over an alphabet of size ?

  • a)
  • b)
  • c)
  • d)
Answer

c) — In the worst case (no shared prefixes), there are nodes, each potentially storing child pointers. With shared prefixes, the actual space is typically much less.

4. What technique does Manacher's algorithm use to achieve for finding the longest palindromic substring?

  • a) Dynamic programming
  • b) Rolling hash
  • c) Exploiting mirror symmetry of palindromes within a known palindrome boundary
  • d) Divide and conquer
Answer

c) Exploiting mirror symmetry of palindromes within a known palindrome boundary — When expanding palindromes, Manacher's algorithm reuses information from the mirror position of the current center within the rightmost known palindrome, avoiding redundant character comparisons.

5. Edit distance is an example of which DP pattern?

  • a) 1D linear sequence
  • b) 2D two-sequence comparison
  • c) Interval DP
  • d) Bitmask DP
Answer

b) 2D two-sequence comparison — Edit distance compares two strings character by character, with dp[i][j] representing the minimum operations to transform the first characters of one string into the first characters of the other.

6. How many character comparisons does the naive algorithm make searching for aab in aaaaaaab (), and how many of them re-read a text character already compared at the previous shift?

Answer

There are shifts. Shifts 0–4 each match aa and fail on the third letter (3 comparisons each), and shift 5 matches fully (3 comparisons): comparisons, the worst case . At every shift after the first, the first two comparisons re-read characters the previous shift had already compared: re-reads. KMP makes at most text comparisons on any input of this length; on this one it makes 13, because after each mismatch it re-tests only the mismatched character, never the aa it already matched.

Practice ladder

Each problem is described in my own words; follow the link for the full statement. The deep lessons have their own, longer ladders.

1. Find the Index of the First Occurrence in a String (LeetCode 28) — First position of a needle in a haystack. Write the naive search, then KMP, and compare them on "a" * 10**5 + "b" with needle "a" * 1000 + "b".

Hint

The naive code above is accepted at LeetCode's limits; the point is to feel the difference on the adversarial input.

2. Repeated Substring Pattern (LeetCode 459) — Is the string a smaller block repeated several times? Teaches periods.

Hint

Either: is a repetition iff occurs in with the first and last characters removed. Or: with , the answer is yes iff and (KMP).

3. Rotate String (LeetCode 796) — Is one string a rotation of another? Teaches the trick.

Hint

Same length, and occurs in . Any linear matcher makes it .

4. Implement Trie (LeetCode 208) — Insert, search and prefix search. The trie code above is a full solution.

Hint

Store an end-of-word flag separately from "has children": "app" can be a word and a prefix of "apple".

5. Repeated DNA Sequences (LeetCode 187) — Every 10-letter window that occurs twice. Teaches rolling hashes (String Hashing).

Hint

2 bits per letter, 20 bits per window: an exact rolling hash.

6. Longest Happy Prefix (LeetCode 1392) — Longest proper prefix that is also a suffix. Teaches the prefix function or hashing.

Hint

The answer has length .

7. Word Search II (LeetCode 212) — Find which dictionary words can be traced on a letter grid. Teaches pruning a search with a trie.

Hint

Put the words in a trie and DFS the grid while walking the trie; abandon a path as soon as the trie has no child for the next letter, and delete found words from the trie.

8. Stream of Characters (LeetCode 1032) — After each new character of a stream, does some word end here? Teaches multi-pattern matching (Aho–Corasick).

Hint

A trie of reversed words, walked backwards from the newest character, works; Aho–Corasick answers each character in amortised .

9. Longest Palindromic Substring (LeetCode 5) — The classic. Expand around centres in , or Manacher in .

Hint

The Manacher code above is a full solution; test it on even-length answers such as "cbbd".

10. Edit Distance (LeetCode 72) — Minimum insertions, deletions and replacements. The DP above is a full solution.

Hint

Fill row by row; dp[i][0] = i and dp[0][j] = j are the base cases.

Sources

  • Donald E. Knuth, James H. Morris, Vaughan R. Pratt, "Fast pattern matching in strings", SIAM Journal on Computing 6(2), 1977.
  • Richard M. Karp and Michael O. Rabin, "Efficient randomized pattern-matching algorithms", IBM Journal of Research and Development 31(2), 1987.
  • Alfred V. Aho and Margaret J. Corasick, "Efficient string matching: an aid to bibliographic search", Communications of the ACM 18(6), 1975.
  • Udi Manber and Gene Myers, "Suffix arrays: a new method for on-line string searches", SIAM Journal on Computing 22(5), 1993.
  • Glenn Manacher, "A new linear-time on-line algorithm for finding the smallest initial palindrome of a string", Journal of the ACM 22(3), 1975.
  • The worked numbers on this page (the naive trace, the comparison counts on random text and on , and the corrected KMP and suffix-array examples) were produced by running the code shown; the visualizer is generated by scripts/traces/naive_matching.py.

Next lesson: String Hashing in Depth

Related: Strings in Depth · Tries · Hash Tables · Dynamic Programming · Course home