skip to content

A regex engine can run a pattern by backtracking or by advancing a set of states - how does each execute a match?

level: middleimportance: must knowfreq 64%

answer

  1. two ways to schedule the same search
  2. one branch at a time versus all at once
  3. rewinding to a saved input position
  4. a set of live states per character
  5. input length times pattern size

basics

~10 s

A backtracking engine explores one alternative at a time and rewinds the input when a branch fails. A state-set engine advances every live alternative together, consuming each input character exactly once.

solid answer

~40 s

Both run the same pattern; they schedule the search differently. A backtracking engine walks the pattern recursively: at each alternation or quantifier it saves the input position, commits to one branch, and on failure restores that position and tries the next - so one input character can be re-examined many times. A state-set engine compiles the pattern into a machine and keeps the `set` of states the input so far is consistent with; for each character it computes the next set in a single step and never rewinds. That gives a time bound proportional to input length times pattern size, against a backtracking worst case that can grow exponentially in input length. The price is features: the set remembers positions in the pattern, not the text matched so far.

code

pseudocode · 18 lines
pseudocode
function match(node, pos):
    if node is END:
        return pos
    if node is LITERAL c:
        if pos < length(input) and input[pos] == c:
            return match(node.next, pos + 1)
        return FAIL
    if node is ALTERNATION(a, b):
        saved = pos
        r = match(a, saved)            // commit to the first branch
        if r != FAIL: return r
        return match(b, saved)         // rewind, take the second
    if node is STAR(body):
        saved = pos
        r = match(body, saved)         // greedy: one more repetition
        if r != FAIL and r > saved:    // only if it consumed something
            return match(node, r)
        return match(node.next, saved) // zero repetitions, carry on

go deeper

for a junior

Know that a pattern can often match in more than one way, and that one common engine design tries those ways one after another, undoing its work when a try fails.

for a middle

Explain both schedules: saved positions and a retry stack on one side, one set-of-states step per character on the other, and why only the second bounds the work done per input character.

for a senior

Be able to say which architecture is running on your hot path, how you established that, and what the pattern features already in your codebase imply about whether you could change it.

for a principal

Treat the architecture as a platform commitment: a bounded worst case where patterns arrive from elsewhere and latency is promised, feature richness where a small reviewed pattern set is authored offline.

## The choice a pattern leaves open A pattern containing an alternation or a quantifier does not describe one way to match - it describes a **space of possible matches**. A pattern like `a(b|c)*d` leaves open, at every position, whether to take another repetition and which branch of the alternation to take. An engine's architecture is its answer to a single question: **in what order, and with what memory, does it explore that space?** Two answers dominate real engines. ## Backtracking: depth-first, one branch at a time A backtracking engine walks the pattern like a recursive program over the input. - At a **choice point** - an alternation, a quantifier, an optional element - it saves the current input position (and the capture state) and commits to one branch. - It descends until the branch either reaches the end of the pattern (success) or meets a character that does not match (failure). - On failure it **pops back** to the most recent saved choice point, restores the saved input position, and takes the next alternative there. - If every alternative at every choice point is exhausted and the pattern is unanchored, the attempt begins again one character further along. The consequence that matters is that **a single input character can be examined many times** - once for every partial path that reaches it. On ordinary patterns over ordinary text that number is small, and the engine is quick because each individual step is cheap. When the pattern's choice structure is ambiguous, the number of paths can grow much faster than the input does, and the work per record stops being predictable from the record's length. ## State-set simulation: breadth-first, one step per character The other architecture compiles the pattern into a machine and keeps **the set of machine states that the input read so far is consistent with**. For each input character it computes the next set from the current one, in one step, and moves on. It never rewinds, because it never committed to a branch: every branch is already represented inside the set. Two properties follow directly: - The number of live states is **at most the size of the pattern**, because the set is a subset of the machine's states. Duplicate paths collapse - two routes that arrive at the same state become one entry. - Each input character is consumed **exactly once**, so total time is bounded by **input length times pattern size**, whatever shape the pattern has. That is the whole trade in one sentence: the set forgets *how* it reached a state, which is what makes it cheap, and also what makes some pattern features impossible on it. ## Cost and capability, side by side | Property | Backtracking | State-set simulation | |---|---|---| | Work per input character | Unbounded; depends on paths explored | One step over the live set | | Worst-case time | Can grow exponentially in input length | Input length times pattern size | | Memory | One stack entry per pending choice point | The live set, bounded by pattern size | | Remembers matched text | Yes - it is executing one candidate match | No - only positions within the pattern | | Per-step constant factor | Very small | Larger, unless transitions are cached | ## Why both architectures survive Neither is strictly better, which is why engines of both kinds are in wide use and some implementations carry both. 1. **Backtracking is fast on the common case and rich in features.** Because it is literally executing one candidate match, it holds the matched text, so backreferences, arbitrary assertions and recursive sub-patterns come naturally. 2. **State-set simulation sells a guarantee.** Its cost is a function of two numbers you can measure - record length and pattern size - which is what makes it possible to put pattern matching on a latency-budgeted path at all. 3. **Hybrids dispatch.** An implementation can inspect a compiled pattern, run it on the one-pass machine when it uses no feature that needs the matched text, and route it to a backtracking path when it does. Ecosystems differ in whether they offer this and in which features they place on which side. ## Where the difference actually shows up On a filter applying a large pattern set to every record, the architecture reveals itself in the *shape* of the latency distribution rather than its mean. A backtracking engine tends to give an excellent median with a tail that is a property of the data rather than of the traffic rate - one unusual record can cost orders of magnitude more than its neighbours. A one-pass engine gives a flatter distribution whose worst case you can compute before deploying. So the choice is less a performance question than a question about **which of the two behaviours you are able to promise**.

  • Does a backtracking engine ever run in linear time?
    Usually it effectively does. On ordinary patterns and ordinary input it finds the match after few retries, and its per-step constant is small, so it often beats a one-pass engine outright. The worst case is not the common case; it is the case that unlucky or hostile data selects. A one-pass engine buys a guarantee, not a better average.
  • Where does a backtracking engine's memory go?
    Into the retry stack: one saved position, plus capture state, for every pending choice point. Depth grows with the number of undecided choices, so a long repetition over a long input can hold stack proportional to the input length, and an implementation using native recursion can exhaust its stack before the time cost becomes visible.
  • Can one implementation contain both architectures?
    Yes, and several do. The compiler inspects the pattern: if it uses nothing that requires the text matched so far, it runs on the one-pass machine; otherwise it goes to the backtracking path. Ecosystems differ in whether this dispatch exists and whether you can see or control which path a pattern took.

Backtracking is one explorer in a maze with a ball of string, walking back to the last junction after every dead end. State-set simulation is water poured in at the entrance: every corridor fills at the same rate, but the water cannot tell you which way it came.

saying these in an interview costs you the question

  • Thinks backtracking rescans from the start of the input on every failure.
  • Believes a state-set engine just tries the same alternatives faster.
  • Assumes both architectures accept exactly the same pattern features.
  • Claims the one-pass engine always wins on real production workloads.
  • Thinks the live state set records the text matched so far.