On this page

Capstone: A Mini grep and Full-Text Search Engine

Every programmer runs a string-search engine dozens of times a day. grep -F looks for many fixed strings at once, grep -E runs a regular expression over every line, and the search box of a code host or an e-book reader answers "where does this phrase occur?" in milliseconds by consulting an index built ahead of time. In this capstone you build all three from the algorithms of Module 7, test them against brute force and against the real grep, and then measure what each design costs and buys.

This is Module 7 applied. Part 1 uses the automaton from Aho–Corasick. Part 2 builds the index from Suffix Arrays & LCP and races it against KMP and the naive scan from the module overview. Part 3 reuses the Thompson engine from How Regex Engines Work. Part 4 is about numbers: when does an index pay for itself, and what does "linear time" mean when the alternative is written in C? The surprises are the point. A pure-Python Aho–Corasick loses to C's str.find on 10 patterns and beats it by a factor of 7 on 1,000; a suffix array answers a query 7,000 times faster than KMP but needs 160 MiB of scratch memory to build on a 1 MB text; and Python's backtracking re is 40 times faster than our NFA on a normal regex and 20,000 times slower on a hostile one.

Goal

Build a small command-line tool, minigrep, with three modes and one benchmark:

  1. minigrep -F WORD… FILE prints every line (with its line number, like grep -n) that contains at least one of the words, using one Aho–Corasick pass over the file rather than one search per word.
  2. minigrep -S WORD… FILE builds a suffix array of the whole file once and then answers "how many times, and where, does this string occur?" for each query by binary search.
  3. minigrep -E REGEX FILE prints every line containing a match of a regular expression (literals, ., *, +, ?, |, parentheses), using Thompson NFA simulation, so that no pattern can make it take exponential time.
  4. minigrep --bench measures index build time, memory and query latency for every mode against the simple alternatives, on corpora of 250,000 and 1,000,000 characters.

Every mode must agree with a brute-force reference on random inputs, and the -F and -E modes must print exactly what grep -nF/grep -nE print on the same file. The reference solution is a single tested Python file using only the standard library.

Requirements

  • Fixed-string mode. Build the Aho–Corasick automaton (trie + failure links by BFS + dictionary-suffix links) once. Report every occurrence, overlaps included (he, she and hers all occur in ushers). For grep output, stop scanning a line at its first hit.
  • Index mode. Suffix array by prefix doubling: with a comparison sort is fine; with radix sort is a stretch goal. Store it compactly (4 bytes per suffix). Queries: count(p) and locate(p) in by two binary searches. Also compute the LCP array with Kasai's algorithm and report the longest repeated substring.
  • Regex mode. Full-match engine from the regex lesson turned into a search: a match may start anywhere in the line. Must run in .
  • Baselines. A pure-Python naive matcher (character by character), KMP, and the C-implemented str.find/str.count and re, so you can separate "better algorithm" from "faster language".
  • Benchmark. Same inputs for every method, answers asserted equal, best of 3 runs for anything fast, a separate run under tracemalloc for peak memory (tracing slows allocation; never time a traced run).
  • Tests. The acceptance tests below pass.

Getting the data

Everything runs offline, and nothing large is downloaded.

  • The golden text for the acceptance tests is embedded in the reference solution: the first two paragraphs of Charles Dickens's A Tale of Two Cities (1859, public domain), 945 characters wrapped at 64 columns into 17 lines (10 for the first paragraph, a blank line, 6 for the second). It is short enough to check every expected number by hand.
  • The benchmark corpus is generated: a deterministic stream of pseudo-English, using about 150 common English words plus 5,000 invented words built from syllables (bahudunu, cahesu, …), drawn with Zipf-like weights (the -th most common word appears with probability proportional to , roughly like real text), in lines of at most 72 characters. A fixed seed makes every run identical. 1,000,000 characters contain 5,127 distinct words in 14,180 lines.
  • A real corpus, if you want one: any text file. This repository's own lesson files make a good one, for example cat docs/algorithms/string-algorithms/*.md > corpus.txt (about 820 KB of Markdown when this page was written). Or download a book from Project Gutenberg yourself. The CLI takes any file.
flowchart LR
    FILE["text file"] --> MODE{"mode"}
    MODE -->|"-F words"| AC["Aho-Corasick automaton, one pass"]
    MODE -->|"-S queries"| SA["suffix array, built once"]
    MODE -->|"-E regex"| NFA["Thompson NFA, set simulation"]
    AC --> LINES["matching lines, numbered"]
    NFA --> LINES
    SA --> HITS["count and offsets per query"]
    LINES --> CHECK["compare with grep -n"]
    HITS --> CHECK2["compare with KMP and naive"]

The staged plan

Part 1 — Many fixed strings with Aho–Corasick

The problem. Given patterns of total length and a text of length , report every occurrence of every pattern. Running KMP times costs . The Aho–Corasick automaton reads the text once: , independent of .

Step 1: trie. Insert every pattern into a trie; mark each pattern's end node with its index.

Step 2: failure links by BFS. The failure link of node (spelling string ) points to the node for the longest proper suffix of that is also in the trie. Process nodes in BFS order so the parent's link is ready: follow the parent's failure chain until some node has a child on the same character.

Step 3: dictionary-suffix links. From , the nearest node along the failure chain that ends a pattern. Following only these links when reporting matches costs per reported occurrence, instead of walking the whole failure chain at every text position.

Step 4: scan. At each character, follow failure links until the current node has a child on it (or you are at the root), step, then report the node's own patterns and those along its dictionary links. Report the start of each occurrence: i - len(pattern) + 1.

Step 5: grep semantics. Real grep is line-oriented: a match never spans a newline, and each matching line prints once. Split the file on \n, run the automaton per line, and stop at the first hit. Notice what this does to counts: in the golden text, we had occurs twice, but the second occurrence is split across a line break (… we / had nothing …), so a scan of the whole text with the newline as an ordinary character finds it once. The acceptance tests pin this down so you notice it.

Check against the real grep

diff <(python3 capstone.py -F KMP Z-algorithm corpus.txt) <(grep -nE 'KMP|Z-algorithm' corpus.txt) must print nothing. While writing this page, both produced the same 165 lines on the 820 KB Markdown corpus.

Part 2 — A suffix-array index, against naive and KMP

The idea. A suffix array (Manber and Myers, 1990) is the list of starting positions of all suffixes of the text, sorted alphabetically. For banana the suffixes sorted are a, ana, anana, banana, na, nana, so the array is . Every occurrence of a pattern is the start of a suffix that begins with , and in sorted order all such suffixes sit in one contiguous block. Two binary searches find the block's ends: per query, after which the block's size is the count and its entries are the positions.

Step 1: build by prefix doubling. Sorting the suffixes as strings (sorted(range(n), key=lambda i: text[i:])) is correct and fine for tests, but it copies characters. Instead:

  1. Give each position a rank = its character code.
  2. Round : sort positions by the pair (rank of , rank of , or "nothing" if past the end). After sorting, positions with equal pairs get equal new ranks. Now ranks order the suffixes by their first characters.
  3. Stop when all ranks are distinct.

Each round is one sort: . The number of rounds is about of the longest repeated substring, at most . The reference encodes each pair as one integer rank[i] * base + rank[i + k] + 1 so Python's built-in sort can be used with a key list. (A bug made while writing this page: using n + 2 as the base in the first round, when ranks are still character codes like 8212 for an em dash, which can exceed . The random tests against sorted caught it.)

Step 2: queries. lower = first suffix whose first m characters are >= p, upper = first suffix whose first m characters are > p. Count is upper - lower, positions are sorted(sa[lower:upper]).

Step 3: LCP and the longest repeat. Kasai's algorithm (Kasai et al., 2001) computes, in , the length of the longest common prefix of each pair of neighbouring suffixes in the array. The longest repeated substring is the largest LCP value. In the golden text it is here were a king with a large (29 characters), from "There were a king with a large jaw" and "there were a king with a large jaw": the capital T is why the repeat starts at h.

Step 4: the baselines. Write a naive matcher and KMP in pure Python, returning all (overlapping) occurrence positions. Assert that locate(p) equals both on random inputs. Then time all three, plus str.count (C, non-overlapping; fine for the timing).

Part 3 — A regex mode on the Thompson NFA

Take the engine from How Regex Engines Work. It decides whether the whole string matches. grep needs search: does a match start anywhere in the line? Two equivalent fixes:

  1. Prefix the pattern with .*. Simple, and the NFA stays linear in size.
  2. Inside the simulation, add the start state's ε-closure to the set at every position ("a new thread starts here"), and return as soon as the accept state appears.

The reference does option 2, which also lets it stop at the earliest match end. The cost per line is for a line of length and a pattern of size , whatever the pattern. Test it against re.search on random patterns and lines, then against grep -nE on a real file, and finally feed it (a+)+b against long runs of a. Python's re takes 0.6 s at 24 characters and doubles with each extra one; yours should not notice.

Pattern syntax is a subset

The engine supports literals, ., *, +, ?, |, () and \ escapes. No character classes, anchors, {m,n} or backreferences. When you compare with grep -E, use patterns in that subset. Adding [a-z] is a good first extension (one labelled arrow with a set label).

Part 4 — Benchmark and measure

For corpus sizes 250,000 and 1,000,000 characters:

  1. Multi-pattern. For random distinct words from the corpus: Aho–Corasick build time and scan time versus calls of str.find in a loop (C, but passes). Assert the same occurrence lists.
  2. Index. Suffix-array build time; peak memory during the build (separate tracemalloc run); memory kept afterwards. Then 400 queries (200 single words and 200 two-word phrases): average latency of SuffixIndex.count, versus KMP and naive (5 queries each; they are slow) and str.count.
  3. Regex. Time grep_regex versus re.search per line for (he|she|it) (was|had), and assert the same matching lines. Then the pathological (a+)+b on lines of 16, 20 and 24 as.
  4. Explain each number: what is the asymptotic cost, and what is the constant factor of Python versus C?

Milestones

#MilestoneDone when
1Aho–Corasickoccurrence lists equal the brute force on 300 random small cases; ushers gives she@1, he@2, hers@2
2-F modeline numbers on the golden text match; output identical to grep -nF/grep -nE on a real file
3Suffix arrayequals sorted(range(n), key=lambda i: s[i:]) on 300 random strings; banana → [5, 3, 1, 0, 4, 2]
4Queries and LCPlocate = KMP = naive on random strings; LCP of banana is [0, 1, 3, 0, 0, 2]
5Regex search modeagrees with re.search on 2,000 random patterns × 10 lines; (a+)+b on 5,000 as finishes in well under 2 s
6CLI-F, -S, -E wired to the functions above
7Benchmarka table of build time, memory and latency for both corpus sizes, with an explanation

Acceptance tests

Your tool passes when:

TestExpected
Aho–Corasick on the golden text, patterns it was, was, age, season, of, we had, king, queen, face, hecounts 10, 12, 2, 2, 16, 1, 2, 2, 2, 22
The same occurrences vs. str.find for each patternidentical sorted (start, pattern) lists
he, she, his, hers in ushers(1, she), (2, he), (2, hers)
-F king Heaven on the golden textlines 6, 12, 13
300 random texts over {a, b} with up to 6 patternsAho–Corasick = brute force
Suffix array, 300 random strings over {a, b, c} (length ≤ 60)equals sorting the suffixes
bananaSA [5, 3, 1, 0, 4, 2], LCP [0, 1, 3, 0, 0, 2], longest repeat ana
Index on the golden textcount("it was") = 10, count("It was") = 1, count("zebra") = 0, count("") = 945, locate("epoch") = positions from re.finditer
Longest repeated substring of the golden texthere were a king with a large
`-E "(kingqueen) with a (large
`-E "epochseason"`
-E zebrano lines
2,000 random patterns over {a, b, .} with `* + ?()`, 10 random lines each
(a+)+b against 5,000 asno match, in under 2 s (it takes about 2 ms)
make_corpus(10_000) twiceidentical, exactly 10,000 characters

The golden text, as the reference wraps it (line numbers on the left):

 1  It was the best of times, it was the worst of times, it was the
 2  age of wisdom, it was the age of foolishness, it was the epoch
 3  of belief, it was the epoch of incredulity, it was the season of
 4  Light, it was the season of Darkness, it was the spring of hope,
 5  it was the winter of despair, we had everything before us, we
 6  had nothing before us, we were all going direct to Heaven, we
 7  were all going direct the other way—in short, the period was so
 8  far like the present period, that some of its noisiest
 9  authorities insisted on its being received, for good or for
10  evil, in the superlative degree of comparison only.
11
12  There were a king with a large jaw and a queen with a plain
13  face, on the throne of England; there were a king with a large
14  jaw and a queen with a fair face, on the throne of France. In
15  both countries it was clearer than crystal to the lords of the
16  State preserves of loaves and fishes, that things in general
17  were settled for ever.

Check a few by hand. it was (lower case) appears 9 times in the first paragraph and once in the second (it was clearer), so 10; It was once. he counts 22 because it hides inside words such as the, there and other: Aho–Corasick reports substrings, not words. epoch|season hits lines 2, 3 and 4: line 3 contains both epoch and season and prints once.

Reference solution

Reference solution (Python, tested)

One file, standard library only. python3 capstone.py runs every acceptance test in under a second; python3 capstone.py --bench runs Part 4 (about 25 seconds); python3 capstone.py -F|-S|-E … FILE is the CLI.

"""Module 7 capstone reference solution: a mini grep and full-text search engine.

  python3 capstone.py                          run the acceptance tests
  python3 capstone.py --bench                  run Part 4 (about a minute)
  python3 capstone.py -F WORD... FILE          lines containing any WORD (Aho-Corasick)
  python3 capstone.py -E REGEX FILE            lines containing a match (Thompson NFA)
  python3 capstone.py -S WORD... FILE          suffix-array lookups: count and offsets

Standard library only. Python 3.10+.
"""
import random
import re
import sys
import textwrap
import time
import tracemalloc
from array import array
from collections import deque

# ------------------------------------------------------------------ the corpus

# Charles Dickens, A Tale of Two Cities (1859), opening paragraphs. Public domain.
DICKENS = textwrap.fill(
    "It was the best of times, it was the worst of times, it was the age of "
    "wisdom, it was the age of foolishness, it was the epoch of belief, it was "
    "the epoch of incredulity, it was the season of Light, it was the season of "
    "Darkness, it was the spring of hope, it was the winter of despair, we had "
    "everything before us, we had nothing before us, we were all going direct to "
    "Heaven, we were all going direct the other way—in short, the period was "
    "so far like the present period, that some of its noisiest authorities "
    "insisted on its being received, for good or for evil, in the superlative "
    "degree of comparison only.", 64) + "\n\n" + textwrap.fill(
    "There were a king with a large jaw and a queen with a plain face, on the "
    "throne of England; there were a king with a large jaw and a queen with a "
    "fair face, on the throne of France. In both countries it was clearer than "
    "crystal to the lords of the State preserves of loaves and fishes, that "
    "things in general were settled for ever.", 64) + "\n"

VOCAB = ("the of and to a in that was it his he i with as had for you not be her "
         "on at by which have or from this him but all she they were my are me one "
         "their so an said them we who would been will no when there if more out up "
         "into do any your what has man could other than our some very time upon "
         "about may its only now like little then can should made did us such great "
         "before must two these see know over much down after first mr good men own "
         "never most old shall day where those came come himself way work life "
         "without go make well through being long say might how am too even "
         "again many back here think every people went yet just thought same "
         "regular expression automaton suffix array pattern search index query "
         "string algorithm kmp aho corasick thompson").split()


def make_corpus(n_chars: int, seed: int = 2026) -> str:
    """Deterministic pseudo-English: the common words above plus 5,000 invented
    ones built from syllables, drawn with Zipf weights, lines of <= 72 chars."""
    rng = random.Random(seed)
    syllables = [c + v for c in "bcdfghklmnprstvw" for v in "aeiou"]
    invented = set()
    while len(invented) < 5000:
        invented.add("".join(rng.choices(syllables, k=rng.randint(1, 4))))
    vocab = VOCAB + sorted(invented - set(VOCAB))
    weights = [1 / (r + 1) for r in range(len(vocab))]
    out, line, size = [], [], 0
    while size < n_chars:
        words = rng.choices(vocab, weights, k=256)
        for w in words:
            if sum(map(len, line)) + len(line) + len(w) > 72:
                s = " ".join(line) + "\n"
                out.append(s)
                size += len(s)
                line = []
            line.append(w)
    return "".join(out)[:n_chars]


# ------------------------------------------------- Part 1: Aho-Corasick (-F mode)

class AhoCorasick:
    """Trie of the patterns + failure links (BFS) + dictionary-suffix links."""

    def __init__(self, patterns: list[str]) -> None:
        self.patterns = patterns
        self.goto: list[dict[str, int]] = [{}]
        self.fail = [0]
        self.out: list[list[int]] = [[]]    # patterns ending exactly here
        self.dict_link = [-1]               # nearest proper suffix state with output
        for idx, p in enumerate(patterns):
            if not p:
                raise ValueError("empty pattern")
            node = 0
            for ch in p:
                nxt = self.goto[node].get(ch)
                if nxt is None:
                    nxt = len(self.goto)
                    self.goto[node][ch] = nxt
                    self.goto.append({})
                    self.fail.append(0)
                    self.out.append([])
                    self.dict_link.append(-1)
                node = nxt
            self.out[node].append(idx)
        queue = deque(self.goto[0].values())    # depth-1 nodes fail to the root
        while queue:
            u = queue.popleft()
            for ch, v in self.goto[u].items():
                f = self.fail[u]
                while f and ch not in self.goto[f]:
                    f = self.fail[f]
                self.fail[v] = self.goto[f].get(ch, 0)
                w = self.fail[v]
                self.dict_link[v] = w if self.out[w] else self.dict_link[w]
                queue.append(v)

    def finditer(self, text: str):
        """Yield (start, pattern_index) for every occurrence, overlaps included."""
        node, goto, fail = 0, self.goto, self.fail
        for i, ch in enumerate(text):
            while node and ch not in goto[node]:
                node = fail[node]
            node = goto[node].get(ch, 0)
            v = node if self.out[node] else self.dict_link[node]
            while v > 0:
                for idx in self.out[v]:
                    yield i - len(self.patterns[idx]) + 1, idx
                v = self.dict_link[v]

    def count(self, text: str) -> list[int]:
        counts = [0] * len(self.patterns)
        for _, idx in self.finditer(text):
            counts[idx] += 1
        return counts


def naive_multi(text: str, patterns: list[str]) -> list[tuple[int, int]]:
    """Every (start, pattern_index), by checking each pattern at each position."""
    hits = []
    for idx, p in enumerate(patterns):
        start = text.find(p)
        while start != -1:
            hits.append((start, idx))
            start = text.find(p, start + 1)
    return sorted(hits)


def grep_fixed(text: str, patterns: list[str]) -> list[tuple[int, str]]:
    """(line number, line) for each line containing at least one pattern."""
    ac = AhoCorasick(patterns)
    return [(n, line) for n, line in enumerate(text.split("\n"), 1)
            if next(ac.finditer(line), None) is not None]


# ---------------------------------------------------- Part 2: suffix array (-S)

def suffix_array(s: str) -> array:
    """Prefix doubling: sort suffixes by their first 2^k characters, k = 0, 1, ...
    O(n log^2 n) with a comparison sort; stops once all ranks are distinct."""
    n = len(s)
    sa = list(range(n))
    rank = [ord(c) for c in s]
    k = 1
    while True:
        base = max(rank, default=0) + 2         # "digits" of the two-part key
        key = [rank[i] * base + (rank[i + k] + 1 if i + k < n else 0) for i in range(n)]
        sa.sort(key=key.__getitem__)
        new_rank = [0] * n
        for j in range(1, n):
            new_rank[sa[j]] = new_rank[sa[j - 1]] + (key[sa[j]] != key[sa[j - 1]])
        rank = new_rank
        if n == 0 or rank[sa[-1]] == n - 1:     # all distinct: fully sorted
            return array("i", sa)
        k *= 2


def lcp_array(s: str, sa) -> array:
    """Kasai: lcp[j] = longest common prefix of suffixes sa[j-1] and sa[j]."""
    n = len(s)
    rank = [0] * n
    for j, i in enumerate(sa):
        rank[i] = j
    lcp, h = array("i", [0] * n), 0
    for i in range(n):
        if rank[i] > 0:
            j = sa[rank[i] - 1]
            while i + h < n and j + h < n and s[i + h] == s[j + h]:
                h += 1
            lcp[rank[i]] = h
            if h:
                h -= 1
        else:
            h = 0
    return lcp


class SuffixIndex:
    def __init__(self, text: str) -> None:
        self.text = text
        self.sa = suffix_array(text)

    def _bound(self, p: str, upper: bool) -> int:
        """First suffix whose m-prefix is >= p (or > p when upper)."""
        lo, hi, m, t, sa = 0, len(self.sa), len(p), self.text, self.sa
        while lo < hi:
            mid = (lo + hi) // 2
            head = t[sa[mid]:sa[mid] + m]
            if head < p or (upper and head == p):
                lo = mid + 1
            else:
                hi = mid
        return lo

    def count(self, p: str) -> int:
        return self._bound(p, True) - self._bound(p, False)

    def locate(self, p: str) -> list[int]:
        lo, hi = self._bound(p, False), self._bound(p, True)
        return sorted(self.sa[lo:hi])


def longest_repeated_substring(text: str) -> str:
    sa = suffix_array(text)
    lcp = lcp_array(text, sa)
    j = max(range(len(lcp)), key=lcp.__getitem__, default=0)
    return text[sa[j]:sa[j] + lcp[j]] if text else ""


def naive_find_all(text: str, p: str) -> list[int]:
    """Character-by-character, in pure Python: the baseline."""
    n, m = len(text), len(p)
    out = []
    for i in range(n - m + 1):
        j = 0
        while j < m and text[i + j] == p[j]:
            j += 1
        if j == m:
            out.append(i)
    return out


def kmp_find_all(text: str, p: str) -> list[int]:
    m = len(p)
    pi = [0] * m
    for i in range(1, m):
        k = pi[i - 1]
        while k and p[i] != p[k]:
            k = pi[k - 1]
        pi[i] = k + (p[i] == p[k])
    out, j = [], 0
    for i, ch in enumerate(text):
        while j and ch != p[j]:
            j = pi[j - 1]
        if ch == p[j]:
            j += 1
        if j == m:
            out.append(i - m + 1)
            j = pi[j - 1]
    return out


# ------------------------------------------------ Part 3: regex mode (-E), Thompson

ANY = object()


def compile_regex(pattern: str):
    """Thompson's construction for literals, ., *, +, ?, |, ( ) and \\ escapes.
    Returns (label, target, eps, start, accept) as parallel lists."""
    label, target, eps = [], [], []
    pos = 0

    def new():
        label.append(None)
        target.append(-1)
        eps.append([])
        return len(label) - 1

    def peek():
        return pattern[pos] if pos < len(pattern) else None

    def alt():
        nonlocal pos
        s1, a1 = concat()
        while peek() == "|":
            pos += 1
            s2, a2 = concat()
            s, a = new(), new()
            eps[s] += [s1, s2]
            eps[a1].append(a)
            eps[a2].append(a)
            s1, a1 = s, a
        return s1, a1

    def concat():
        if peek() in (None, "|", ")"):
            s = new()
            return s, s
        s, a = repeat()
        while peek() not in (None, "|", ")"):
            s2, a2 = repeat()
            eps[a].append(s2)
            a = a2
        return s, a

    def repeat():
        nonlocal pos
        s1, a1 = atom()
        while peek() in ("*", "+", "?"):
            op = pattern[pos]
            pos += 1
            s, a = new(), new()
            eps[s].append(s1)
            if op != "+":
                eps[s].append(a)
            eps[a1].append(a)
            if op != "?":
                eps[a1].append(s1)
            s1, a1 = s, a
        return s1, a1

    def atom():
        nonlocal pos
        c = peek()
        if c is None or c in "*+?":
            raise ValueError(f"expected an atom at {pos}")
        pos += 1
        if c == "(":
            frag = alt()
            if peek() != ")":
                raise ValueError("missing )")
            pos += 1
            return frag
        lab = ANY if c == "." else c
        if c == "\\":
            if peek() is None:
                raise ValueError("trailing backslash")
            lab = pattern[pos]
            pos += 1
        s, a = new(), new()
        label[s], target[s] = lab, a
        return s, a

    start, accept = alt()
    if pos != len(pattern):
        raise ValueError(f"unexpected {pattern[pos]!r} at {pos}")
    return label, target, eps, start, accept


def nfa_search(nfa, line: str) -> bool:
    """Is there a match anywhere in the line? Unanchored: a new thread starts
    at every position (the implicit leading .*), and we stop at the first accept."""
    label, target, eps, start, accept = nfa

    def add(states, s):
        stack = [s]
        while stack:
            u = stack.pop()
            if u not in states:
                states.add(u)
                stack.extend(eps[u])

    cur = set()
    add(cur, start)
    for ch in line:
        if accept in cur:
            return True
        nxt = set()
        for s in cur:
            lab = label[s]
            if lab is ANY or lab == ch:
                add(nxt, target[s])
        add(nxt, start)                       # a match may also start here
        cur = nxt
    return accept in cur


def grep_regex(text: str, pattern: str) -> list[tuple[int, str]]:
    nfa = compile_regex(pattern)
    return [(n, line) for n, line in enumerate(text.split("\n"), 1)
            if nfa_search(nfa, line)]


# ------------------------------------------------------------- Part 4: benchmark

def best_of(fn, repeat=3):
    best = float("inf")
    for _ in range(repeat):
        t0 = time.perf_counter()
        result = fn()
        best = min(best, time.perf_counter() - t0)
    return best, result


def benchmark() -> None:
    print(f"Python {sys.version.split()[0]}")
    for size in (250_000, 1_000_000):
        text = make_corpus(size)
        rng = random.Random(size)
        words = sorted(set(text.split()))
        print(f"\n== corpus {size:,} chars, {text.count(chr(10)):,} lines ==")

        for k in (10, 100, 1000):
            patterns = rng.sample(words, k)
            t_build, ac = best_of(lambda: AhoCorasick(patterns))
            t_scan, hits = best_of(lambda: sum(ac.count(text)), 1)
            t_find, nhits = best_of(lambda: len(naive_multi(text, patterns)), 1)
            assert hits == nhits
            print(f"Aho-Corasick, {k} patterns: build {t_build * 1000:.1f} ms, "
                  f"scan {t_scan:.2f} s, {hits:,} hits; {k} x str.find: {t_find:.2f} s")

        t_sa, index = best_of(lambda: SuffixIndex(text), 1)
        tracemalloc.start()
        suffix_array(text)
        peak = tracemalloc.get_traced_memory()[1]
        tracemalloc.stop()
        print(f"suffix array: build {t_sa:.2f} s, peak {peak / 2**20:.0f} MiB while "
              f"building, {index.sa.itemsize * len(index.sa) / 2**20:.1f} MiB kept "
              f"({index.sa.itemsize} bytes per suffix)")

        queries = [rng.choice(words) + " " + rng.choice(words) for _ in range(200)]
        queries += rng.sample(words, min(200, len(words)))
        t_q, c1 = best_of(lambda: [index.count(q) for q in queries])
        t_f, c2 = best_of(lambda: [text.count(q) for q in queries], 1)
        assert c1 == [len(naive_multi(text, [q])) for q in queries]   # overlapping counts
        few = queries[:5]
        t_kmp, _ = best_of(lambda: [kmp_find_all(text, q) for q in few], 1)
        t_naive, _ = best_of(lambda: [naive_find_all(text, q) for q in few], 1)
        print(f"per query: suffix array {t_q / len(queries) * 1e6:.0f} us, "
              f"KMP {t_kmp / len(few) * 1000:.0f} ms, naive {t_naive / len(few) * 1000:.0f} ms, "
              f"str.count (C) {t_f / len(queries) * 1000:.2f} ms")

        regex = "(he|she|it) (was|had)"
        t_nfa, g1 = best_of(lambda: grep_regex(text, regex), 1)
        t_re, g2 = best_of(lambda: [n for n, l in enumerate(text.split("\n"), 1)
                                    if re.search(regex, l)], 1)
        assert [n for n, _ in g1] == g2
        print(f"regex {regex!r}: Thompson {t_nfa:.2f} s, re {t_re * 1000:.0f} ms, "
              f"{len(g1):,} matching lines")

    print("\npathological: (a+)+b against a line of n 'a's (no match)")
    for n in (16, 20, 24):
        line = "a" * n
        t_re, _ = best_of(lambda: re.search("(a+)+b", line), 1)
        t_nfa, _ = best_of(lambda: nfa_search(compile_regex("(a+)+b"), line), 1)
        print(f"  n={n}: re {t_re * 1000:.1f} ms, Thompson {t_nfa * 1000:.2f} ms")


# ------------------------------------------------------------- acceptance tests

def run_tests() -> None:

    # Part 1: Aho-Corasick against brute force
    pats = ["it was", "was", "age", "season", "of", "we had", "king", "queen", "face", "he"]
    ac = AhoCorasick(pats)
    assert sorted(ac.finditer(DICKENS)) == naive_multi(DICKENS, pats)
    counts = dict(zip(pats, ac.count(DICKENS)))
    assert counts == EXPECTED_COUNTS, counts
    assert sorted(AhoCorasick(["he", "she", "his", "hers"]).finditer("ushers")) == \
        [(1, 1), (2, 0), (2, 3)]
    assert [n for n, _ in grep_fixed(DICKENS, ["king", "Heaven"])] == [6, 12, 13]
    rng = random.Random(5)
    for _ in range(300):
        text = "".join(rng.choice("ab") for _ in range(rng.randint(0, 40)))
        ps = list({"".join(rng.choice("ab") for _ in range(rng.randint(1, 4)))
                   for _ in range(rng.randint(1, 6))})
        assert sorted(AhoCorasick(ps).finditer(text)) == naive_multi(text, ps)

    # Part 2: suffix array against sorting and against KMP / naive
    for _ in range(300):
        s = "".join(rng.choice("abc") for _ in range(rng.randint(0, 60)))
        assert list(suffix_array(s)) == sorted(range(len(s)), key=lambda i: s[i:])
        idx = SuffixIndex(s)
        for _ in range(5):
            p = "".join(rng.choice("abc") for _ in range(rng.randint(1, 4)))
            assert idx.locate(p) == kmp_find_all(s, p) == naive_find_all(s, p)
    assert list(suffix_array("banana")) == [5, 3, 1, 0, 4, 2]
    assert list(lcp_array("banana", suffix_array("banana"))) == [0, 1, 3, 0, 0, 2]
    index = SuffixIndex(DICKENS)
    assert index.count("it was") == 10 and index.count("It was") == 1
    assert index.locate("epoch") == [m.start() for m in re.finditer("epoch", DICKENS)]
    assert index.count("zebra") == 0 and index.count("") == len(DICKENS)
    assert longest_repeated_substring(DICKENS) == LONGEST_REPEAT
    assert longest_repeated_substring("banana") == "ana"

    # Part 3: regex mode against re.search, line by line
    assert [n for n, _ in grep_regex(DICKENS, "(king|queen) with a (large|plain)")] == [12, 13]
    assert [n for n, _ in grep_regex(DICKENS, "epoch|season")] == [2, 3, 4]
    assert grep_regex(DICKENS, "zebra") == []
    for _ in range(2000):
        p = random_pattern(rng)
        nfa = compile_regex(p)
        for _ in range(10):
            s = "".join(rng.choice("abc") for _ in range(rng.randint(0, 12)))
            assert nfa_search(nfa, s) == bool(re.search(p, s)), (p, s)
    t0 = time.perf_counter()
    assert not nfa_search(compile_regex("(a+)+b"), "a" * 5000)
    assert time.perf_counter() - t0 < 2.0       # linear: no catastrophic backtracking

    # corpus generator is deterministic
    assert make_corpus(10_000) == make_corpus(10_000) and len(make_corpus(10_000)) == 10_000
    print("all acceptance tests passed")


def random_pattern(rng, depth=0):
    x = rng.random()
    if depth > 3 or x < 0.35:
        return rng.choice("ab.")
    if x < 0.55:
        return random_pattern(rng, depth + 1) + random_pattern(rng, depth + 1)
    if x < 0.70:
        return "(" + random_pattern(rng, depth + 1) + "|" + random_pattern(rng, depth + 1) + ")"
    if x < 0.85:
        return "(" + random_pattern(rng, depth + 1) + ")" + rng.choice("*+?")
    return rng.choice("ab.") + rng.choice("*+?")


# Measured on DICKENS and checked by hand (note "we had" = 1: the second one
# is split across a line break; "he" = 22 counts "the", "there", "her"...).
EXPECTED_COUNTS = {"it was": 10, "was": 12, "age": 2, "season": 2, "of": 16,
                   "we had": 1, "king": 2, "queen": 2, "face": 2, "he": 22}
LONGEST_REPEAT = "here were a king with a large"


def main(argv: list[str]) -> None:
    if not argv:
        run_tests()
    elif argv[0] == "--bench":
        benchmark()
    elif argv[0] in ("-F", "-E", "-S") and len(argv) >= 3:
        text = open(argv[-1], encoding="utf-8").read()
        if argv[0] == "-F":
            for n, line in grep_fixed(text, argv[1:-1]):
                print(f"{n}:{line}")
        elif argv[0] == "-E":
            for n, line in grep_regex(text, argv[1]):
                print(f"{n}:{line}")
        else:
            index = SuffixIndex(text)
            for q in argv[1:-1]:
                print(f"{q!r}: {index.count(q)} at {index.locate(q)[:10]}")
    else:
        print(__doc__)


if __name__ == "__main__":
    main(sys.argv[1:])

Benchmarks and what the numbers should look like

All numbers below were measured while writing this page, with CPython 3.12 on an Apple-silicon Mac. Your absolute times will differ; the ratios and the shapes should not.

Multi-pattern search (1,000,000 characters).

Patterns Aho–Corasick buildAho–Corasick scan × str.find (C)Occurrences
10< 0.1 ms0.04 s0.01 s319
1000.1 ms0.05 s0.05 s3,032
1,0001.0 ms0.08 s0.55 s183,566

How to read it:

  • The scan time barely depends on . From 10 to 1,000 patterns it goes from 0.04 s to 0.08 s, and most of the increase is reporting 183,566 occurrences (many invented words are short and occur inside others). That is the bound you were promised.
  • str.find is linear in . Each call is a fast C scan (CPython uses a Boyer–Moore–Horspool and Two-Way hybrid), so for 10 patterns, ten C passes beat one Python pass by 4×. The crossover is around 100 patterns. At 1,000 patterns the better algorithm wins by 7× despite running in an interpreter that is very roughly 50–100× slower per basic operation than C. Rewritten in C or Rust, Aho–Corasick would win at every above a handful, which is why grep -F with many patterns and tools like ripgrep use it (or SIMD variants such as Teddy).

Suffix-array index.

CorpusBuildPeak memory during buildKept (array('i'))Query (count)KMP (Python)Naive (Python)str.count (C)
250,000 chars0.27 s40 MiB1.0 MiB3 µs5 ms7 ms0.11 ms
1,000,000 chars2.13 s161 MiB3.8 MiB3 µs22 ms32 ms0.46 ms
  • Queries are logarithmic and the scans are linear. Quadrupling the text leaves the suffix-array query at 3 µs (two binary searches of about 20 steps, each comparing a short slice) and multiplies every scan by about 4. At 1 MB the index answers a query about 7,000 times faster than Python KMP and 150 times faster than C's str.count.
  • When does the index pay for itself? Building costs 2.1 s; each scan with str.count costs 0.46 ms. Break-even is about queries. Against a pure-Python scan it is about 100 queries. An index is for a text that is searched many times: a code search server, an e-book, a genome.
  • Memory: the build is the expensive part. The finished array is 4 bytes per character in an array('i'); a Python list of the same integers would cost about 36 bytes per entry (an 8-byte pointer plus a 28-byte int object for values above 256). During the build the reference holds a rank list, a key list of large integers and a list of positions at once: about 170 bytes per character at the peak. A C implementation needs little more than the 4-byte array plus the text itself, and the SA-IS algorithm (Nong, Zhang and Chan, 2009) builds the array in time with little extra space.
  • Build time is superlinear. 0.27 s → 2.13 s for 4× the data (×7.9). Both corpora need the same 5 doubling rounds (their longest repeated substrings are 22 and 23 characters, and 5 rounds compare 32), so the extra comes from the sort's factor and, probably, from the working set (hundreds of MiB of Python objects) falling out of the CPU caches. The number of rounds depends on the longest repeat: on the 820 KB Markdown corpus, where code blocks are copied between lessons, the build took about 3 s.
  • KMP is not faster than naive by much here, and that is expected. On natural-language text the naive matcher fails after one or two characters at almost every position, so both are about steps. KMP's advantage is its worst case (aaaa…ab against aaa…a), not the average case; the module overview traces the bad case.

Regex mode.

TestThompson NFA (Python)re (C, backtracking)
`(hesheit) (was
(a+)+b against 16 as0.02 ms2.6 ms
(a+)+b against 20 as0.01 ms38.6 ms
(a+)+b against 24 as0.03 ms627 ms

On an ordinary pattern, re is about 40× faster: it is C, it scans for the first character with a fast loop, and backtracking on text that rarely matches does little backtracking. On the hostile pattern its time multiplies by about 16 for every 4 characters, while the NFA's stays flat. That is the whole trade-off of How Regex Engines Work in four rows: a backtracking engine is usually fast and occasionally catastrophic; an automaton engine is never catastrophic. Production linear engines (RE2, Rust regex) close the constant-factor gap with lazy DFAs and literal prefilters, which is extension 3.

Extension ideas

  1. Fuzzy search with edit distance. Find all substrings of the text within edit distance of a query (approximate matching). Start with Sellers' algorithm (1980): the edit-distance DP of String DP with row 0 all zeros, so a match may start anywhere, in . Then speed it up with Ukkonen's cut-off (only compute the active prefix of each column) or Myers' bit-parallel algorithm (1999), which processes 64 cells per machine word. For an index-based version, combine the suffix array with "seed and extend": by the pigeonhole principle, if the query is split into pieces, at least one piece occurs exactly; look the pieces up in the index and verify around each hit. This is how many read aligners work. The DP capstone builds the word-level version (spell suggestions).
  2. FM-index. Replace the suffix array with the Burrows–Wheeler transform of the text plus rank tables (Ferragina and Manzini, 2000). Counting the occurrences of takes "backward search" steps, and the whole index can be smaller than the original text when it is compressed. This is the data structure inside the BWA and Bowtie DNA aligners. Build the BWT from your suffix array (bwt[i] = text[sa[i] - 1]), implement backward search, and check its counts against SuffixIndex.count.
  3. Literal prefilters for regex mode. Most real patterns contain a literal every match must include (ERROR.*timeout must contain ERROR and timeout). Extract it from the parse tree, find candidate lines with str.find or Aho–Corasick, and run the NFA only on those lines. This is the main trick behind GNU grep's and ripgrep's speed. Measure the gain on (he|she|it) (was|had) (required literal: a space; weak) and on Thompson.*NFA (strong).
  4. A lazy DFA. Cache (set of NFA states, character) → next set, as in the regex lesson's lab, and measure regex mode again. Expect a large speed-up on long files with small patterns.
  5. Linear-time suffix array. Implement SA-IS or the DC3/skew algorithm (Kärkkäinen and Sanders, 2003) and compare build time and peak memory with prefix doubling. Or implement prefix doubling with radix sort for .
  6. Suffix automaton instead of suffix array. The Suffix Automaton answers "does occur, and how often" in after an build, and it is online (you can append text). Compare its memory with the suffix array's.
  7. Inverted index for word queries. Real search engines (Lucene, Elasticsearch) do not index every substring; they index words, mapping each word to a sorted list of document and position numbers ("postings"), and answer phrase queries by intersecting lists. Build one for the corpus, compare index size and query time with the suffix array, and note which queries each one cannot answer (substrings inside words, for the inverted index).
  8. Memory-mapped files and bytes. Search a file larger than RAM by memory-mapping it (mmap) and working on bytes. Decide what a "character" is when the file is UTF-8 and the pattern contains é.
  9. Character classes, anchors and counted repetition ([a-z], ^, $, x{2,5}) in regex mode, keeping the linear-time guarantee. Expanding x{2,5} multiplies the NFA size, so put a limit on it, as RE2 does.

Further reading: how production tools do it

flowchart LR
    AC["Aho-Corasick 1975: fgrep"]
    TH["Thompson 1968: NFA search in ed"] --> GREP["grep 1973"]
    GREP --> GNU["GNU grep: lazy DFA, Boyer-Moore literals"]
    AC --> RG["ripgrep: Rust regex, Teddy SIMD"]
    TH --> RE2["RE2 2010: lazy DFA + Pike VM"]
    RE2 --> RG
    SA["Suffix arrays 1990"] --> FM["FM-index 2000"]
    FM --> BWA["BWA, Bowtie: DNA read alignment"]
    SA --> CS["Code search: trigram index + regex"]
  • grep and fgrep. Ken Thompson wrote grep in 1973 from the regex code of his ed editor; Alfred Aho wrote egrep (with a DFA) and fgrep (with the Aho–Corasick algorithm, published with Margaret Corasick in Communications of the ACM 18(6), 1975). GNU grep's speed comes from a lazily built DFA, Boyer–Moore-style skipping on a required literal, and avoiding per-line work until a match is found (Mike Haertel's 2010 mailing-list post "why GNU grep is fast" is a classic short read).
  • ripgrep. Andrew Gallant's ripgrep uses Rust's regex crate (lazy DFA, Pike VM, literal extraction, SIMD multi-substring search) and parallel directory walking. His blog post "ripgrep is faster than {grep, ag, git grep, ucg, pt, sift}" (2016) explains each optimisation with benchmarks.
  • Code search. Russ Cox, "Regular Expression Matching with a Trigram Index, or How Google Code Search Worked" (2012): index every 3-character substring, turn a regex into a boolean query over trigrams to find candidate files, then run RE2 on only those. Zoekt and GitHub's code search use related n-gram designs.
  • Suffix arrays and FM-indexes. Udi Manber and Gene Myers, "Suffix arrays: a new method for on-line string searches", SIAM Journal on Computing 22(5), 1993 (conference version 1990). Toru Kasai et al., "Linear-time longest-common-prefix computation in suffix arrays and its applications", CPM 2001. Ge Nong, Sen Zhang, Wai Hong Chan, "Linear suffix array construction by almost pure induced-sorting", DCC 2009 (SA-IS). Paolo Ferragina and Giovanni Manzini, "Opportunistic data structures with applications", FOCS 2000 (the FM-index). Heng Li and Richard Durbin, "Fast and accurate short read alignment with Burrows–Wheeler transform", Bioinformatics 25(14), 2009 (BWA).
  • Approximate matching. Peter Sellers, "The theory and computation of evolutionary distances: pattern recognition", Journal of Algorithms 1(4), 1980. Gene Myers, "A fast bit-vector algorithm for approximate string matching based on dynamic programming", JACM 46(3), 1999. Gonzalo Navarro, "A guided tour to approximate string matching", ACM Computing Surveys 33(1), 2001.
  • The textbook. Dan Gusfield, Algorithms on Strings, Trees, and Sequences, Cambridge University Press, 1997: suffix trees and arrays, Aho–Corasick, approximate matching, and the biology that motivated much of it.

Course navigation. Previous: How Regex Engines Work. Module overview: String Algorithms. Course: DSA: Zero to Mastery. Next: Module 8, Math for Algorithms.