Introduction

Regular expressions are everywhere — they filter emails, validate passwords, search source code and power every text editor you have ever used. The basic idea is simple: describe a pattern, hand it to an engine, get back all the matching strings.

For the pure kind — the regexes that use only concatenation, alternation |, and the Kleene star * — matching is fast. A textbook algorithm converts any such pattern to a non-deterministic finite automaton (NFA), simulates all paths in parallel, and answers in time O(n×m)O(n \times m), where n is the text length and m is the pattern length. No exponential blowup, ever.

But modern regex engines add one extra feature that changes everything: backreferences. A backreference like \1 says "match whatever the first capture group just matched." That tiny addition — the ability to refer back to what was already captured — lifts the matching problem out of the polynomial world entirely. Matching a regex with backreferences against a string is NP-complete (proven by Aho, 1980).

Even without backreferences, PCRE-style engines that use recursive backtracking instead of NFA simulation can be catastrophically slow on carefully crafted inputs. A 30-character string can stall a server for seconds; a 60-character string for hours. That failure mode is called ReDoS — Regular Expression Denial of Service — and it has taken down production systems at Cloudflare, Stack Overflow and many others.

Watch the Backtracking Explode

The classic pathological pattern is (a+)+ matched against a string of aas followed by a character that cannot match (here we use XX). The backtracking engine must explore every way to partition the aas into groups — a number that grows exponentially with the string length. The NFA engine, by contrast, tracks all possible states in parallel and finishes in linear time.

<div class="controls">
  <label>Input length: <b id="lenLabel">10</b> × 'a' + 'X'</label>
  <input type="range" id="lenSlider" min="1" max="28" value="10">
</div>
<div class="results">
  <div class="engine" id="btBox">
    <div class="eng-title">Backtracking engine</div>
    <div class="eng-sub">(simulated — like PCRE)</div>
    <div class="steps" id="btSteps">—</div>
    <div class="label">steps</div>
    <div class="bar-wrap"><div class="bar bt-bar" id="btBar"></div></div>
  </div>
  <div class="engine" id="nfaBox">
    <div class="eng-title">NFA engine</div>
    <div class="eng-sub">(parallel state tracking)</div>
    <div class="steps" id="nfaSteps">—</div>
    <div class="label">steps</div>
    <div class="bar-wrap"><div class="bar nfa-bar" id="nfaBar"></div></div>
  </div>
</div>
<div class="pattern-display">Pattern: <code>(a+)+X</code> on input: <code id="inputDisplay">"aaaaaaaaaX"</code></div>
<div class="note" id="note"></div>
<button id="runBtn" type="button">Run comparison</button>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; padding: 14px; }
.controls { margin-bottom: 1rem; }
.controls label { font-size: .9rem; display: block; margin-bottom: .3rem; }
input[type=range] { width: 100%; accent-color: #1d3557; }
.results { display: flex; gap: 1rem; margin: 1rem 0; }
.engine { flex: 1; background: #f0f4f8; border: 1px solid #cdd9e3; border-radius: 10px;
          padding: .8rem; text-align: center; }
.eng-title { font-weight: 700; font-size: .95rem; color: #1d3557; }
.eng-sub { font-size: .75rem; color: #666; margin-bottom: .5rem; }
.steps { font-size: 2rem; font-weight: 800; color: #1d3557; line-height: 1; margin: .3rem 0; }
#btBox .steps { color: #c92f3c; }
#nfaBox .steps { color: #0a7d33; }
.label { font-size: .7rem; color: #888; text-transform: uppercase; letter-spacing: .05em; }
.bar-wrap { background: #dce4ec; border-radius: 6px; height: 10px; margin-top: .6rem; overflow: hidden; }
.bar { height: 100%; border-radius: 6px; width: 0%; transition: width .4s; }
.bt-bar { background: #e63946; }
.nfa-bar { background: #2d9e5e; }
.pattern-display { font-size: .85rem; color: #444; margin: .5rem 0; }
code { background: #e8eef3; padding: .1rem .35rem; border-radius: 4px; font-size: .85rem; }
.note { font-size: .88rem; min-height: 1.4em; font-weight: 600; margin: .4rem 0; }
.note.warn { color: #b5470a; }
.note.ok { color: #0a7d33; }
button { font: 600 14px system-ui; padding: .45rem 1.1rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; margin-top: .2rem; }
button:hover { background: #16294a; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Demo: compare backtracking step count vs NFA step count for the
// pathological pattern (a+)+X on input "aaa...aX" (all a's, no match).
//
// Backtracking: we simulate how a recursive engine would explore the
// combinatorial tree of partitions of n a's into groups, counting "steps"
// as each attempted match position. The formula is exactly 2^(n-1) attempts
//
// NFA: we count n+1 "steps" = one state-set update per input character.
// This is the linear-time guarantee of NFA simulation.

const MAX_BT_DISPLAY = 1e9; // cap for display; beyond this we show ">1B"

function btSteps(n) {
  // Pattern (a+)+ on "aaa...a" (n a's) then 'X' fails.
  // Number of ways to partition n a's into >= 1 non-empty groups = 2^(n-1).
  // Each partition is one leaf the backtracker must explore, plus internal nodes.
  // Total steps ≈ 2^(n-1) (conservative — real PCRE can be worse due to nested groups).
  if (n <= 0) return 1;
  return Math.pow(2, n - 1);
}

function nfaSteps(n) {
  // NFA processes each character once, maintaining a set of active states.
  // For input of length n+1 (n a's + 'X'): n+1 steps.
  return n + 1;
}

function fmt(x) {
  if (x > MAX_BT_DISPLAY) return '>1,000,000,000';
  if (x >= 1e9) return (x / 1e9).toFixed(2) + 'B';
  if (x >= 1e6) return (x / 1e6).toFixed(2) + 'M';
  if (x >= 1e3) return (x / 1e3).toFixed(1) + 'K';
  return x.toFixed(0);
}

function update() {
  const n = parseInt(document.getElementById('lenSlider').value, 10);
  document.getElementById('lenLabel').textContent = n;
  const inputStr = '"' + 'a'.repeat(n) + 'X"';
  document.getElementById('inputDisplay').textContent = inputStr;
}

function run() {
  const n = parseInt(document.getElementById('lenSlider').value, 10);
  const bt = btSteps(n);
  const nfa = nfaSteps(n);

  document.getElementById('btSteps').textContent = fmt(bt);
  document.getElementById('nfaSteps').textContent = fmt(nfa);

  // Bar widths: log scale for visual clarity
  const logBt = Math.log2(bt + 1);
  const logNfa = Math.log2(nfa + 1);
  const maxLog = Math.max(logBt, logNfa, 1);
  document.getElementById('btBar').style.width = (logBt / maxLog * 100) + '%';
  document.getElementById('nfaBar').style.width = (logNfa / maxLog * 100) + '%';

  const ratio = bt / nfa;
  const note = document.getElementById('note');
  if (bt > MAX_BT_DISPLAY) {
    note.textContent = 'Backtracker would take longer than the age of the universe.';
    note.className = 'note warn';
  } else if (ratio > 1000) {
    note.textContent = i18nFmt('Backtracker is %fmt%× slower than the NFA.', { fmt: fmt(ratio) });
    note.className = 'note warn';
  } else {
    note.textContent = i18nFmt('Backtracker is %fmt%× slower than the NFA.', { fmt: fmt(ratio) });
    note.className = 'note ok';
  }

  // Log to console for verification
  console.log(i18nFmt('n=%n% | BT steps=%bt% | NFA steps=%nfa% | ratio=%toExponential%', { n: n, bt: bt, nfa: nfa, toExponential: (bt/nfa).toExponential(2) }));
}

document.getElementById('lenSlider').addEventListener('input', update);
document.getElementById('runBtn').addEventListener('click', run);
update();
run();
Result
Console

Slide the input length to see how quickly the backtracking step count dwarfs the NFA step count. At length 20 the difference is already staggering. This is not a pathological corner case — any pattern of the form (X+)+ or (X|X)* applied to a non-matching suffix triggers the same explosion.

The Real Complexity

The complexity of regex matching depends sharply on which features the pattern language includes:

  • Pure regexes (no backreferences): matching is in P. Convert the pattern to an NFA with ε-transitions, simulate it on the input string tracking all active states as a set, and you finish in O(n×m)O(n \times m) time. The key insight is that the NFA never needs to revisit a position, because all paths are explored in parallel.
  • Extended regexes with backreferences: matching is NP-complete. The proof (Aho, 1980) reduces 3-SAT to regex matching. A backreference constrains two captured substrings to be identical, which is powerful enough to encode arbitrary satisfiability constraints. So deciding "does string w match pattern p?" when p contains backreferences is exactly as hard as SAT.
  • PCRE with full backtracking: in the worst case the engine explores a tree of choices that is exponential in the input length — not even polynomial. Patterns with nested quantifiers over the same characters (like (a*)* or ([ab]+)*) create this behavior.

The gap is stark: a one-character extension to the syntax — \1 — moves the problem from a clean O(n×m)O(n \times m) algorithm to NP-hardness. Most programmers never encounter the theoretical boundary, but every production regex engine that uses backtracking is one crafted input away from it.

Status: NP-completeness of backreference matching is a proven theorem (Aho 1980, confirmed by Backurs & Indyk 2016). The polynomial NFA algorithm for pure regexes is a standard textbook result. ReDoS is an ongoing applied security concern.

Where It Matters

The gap between NFA-based and backtracking regex engines has concrete consequences across the software stack:

  • Security (ReDoS): a single malicious input can pin a server's CPU at 100% for minutes or longer. Cloudflare's 2019 global outage and Stack Overflow's 2016 downtime were both caused by pathological regexes in hot-path validators. Modern WAFs and input validators must either use NFA engines or run static analysis on every regex before deployment.
  • Static regex analyzers: tools like regexploit, vuln-regex-detector and safe-regex automatically detect patterns that can backtrack exponentially. They are now standard in security-conscious CI pipelines.
  • Compiler lexers: lexer generators (Flex, RE2, Java's Pattern with CANON_EQ disabled) compile patterns to DFAs, sidestepping backtracking entirely. The price is that they reject backreferences — a deliberate trade-off for speed and safety guarantees.
  • Bioinformatics: DNA and protein sequence search tools (BLAST, bowtie) use carefully bounded approximate matching rather than general regex engines, partly to avoid worst-case blowup on repetitive genomic sequences.
  • Program analysis: static analyzers that check whether a string variable can match a regex (to detect injection vulnerabilities) must decide regex membership, and the NP-hardness of extended patterns means they must either restrict the language or resort to heuristics.

Understanding the complexity boundary — pure regex in P, backreferences NP-complete — helps engineers pick the right tool. Prefer NFA-based engines like RE2 or Rust's regex crate when safety matters; reserve PCRE for contexts where the input is trusted and patterns are vetted.

Conclusion

Regular expressions look like a solved problem — and for pure regexes they are. The NFA simulation runs in O(n×m)O(n \times m), never backtracks, and handles any pure pattern you can write. That is a clean, fast, provably correct algorithm.

Add backreferences and the ground shifts. The matching problem becomes NP-complete, the polynomial algorithm breaks down, and real engines fall back to exponential backtracking. The result is not just theoretical: a single unlucky pattern in a server's input validator can render it unresponsive for minutes.

The lesson is simple but easy to forget: the syntax of your pattern determines its complexity class. Reaching for backreferences is reaching for NP-hardness. When you don't need them, an NFA-based engine like RE2 gives you all the expressiveness of pure regexes with an ironclad O(n×m)O(n \times m) guarantee — no crafted input can ever make it slow.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/regular-expression-matching-hardness/Content licensed under CC BY-NC 4.0.