Compile a regex into an NFA by structural recursion (each operator glues sub-automata with epsilon edges, giving ~2m states), then match without ever backtracking: keep the set of every state the NFA could be in and advance them all in lockstep. That set is a bitmask — the same trick as Shift-Or (dart 119). Linear-time matching, and the reason grep is fast where backtracking engines blow up.
THE TECHNIQUE an active-set bitmask, advanced in lockstep
For (a|b)*abb, the active NFA states are one integer’s bits. Each input symbol maps the mask to the next set (move + epsilon-closure). If the accepting bit (state 10) is set at the end, the string matches. No backtracking — all paths advance together. Type a string of a’s and b’s; watch the bitmask walk. live demo
HISTORY & CREDIT 1956 possible, 1960 on paper, 1968 running
“regex matching is inherently exponential / needs backtracking” — true false; Thompson showed O(mn) linear in 1968. The blow-up (ReDoS) is a property of the backtracking engines that abandoned his method. cited
1956 · Kleene proves regular expressions and finite automata equivalent — equivalence-exists, no build procedure. 1960 · McNaughton & Yamada — the first algorithmic regex→state-graph (IRE Trans. EC-9), eight years before Thompson. 1968 · Ken Thompson — “Regular Expression Search Algorithm” (CACM 11(6):419–422): compile regex to an epsilon-NFA, simulate all states at once, generating IBM 7094 code at run time. The named work. 1973 / 2007 · the code becomes grep (1973, the ed command g/re/p); Russ Cox (2007 articles; the RE2 library 2010) revives Thompson’s multi-state simulation after decades of backtracking libraries.
Thompson’s NFA deliberately uses epsilon edges (that is what makes it compositional and linear-sized); the epsilon-free one is Glushkov’s. Thompson, 1968
RECOMMEND FOR I-13 one integer, i13 bitwise, no strings
The matching half is a clean fit: the active state-set is one f64 bitmask, driven by I-13’s bitwise ops over a code-point array:
Recommend:nothing new — input as an f64 code array (branch c==97 vs 98, no strings); the active set is a single f64 integer bitmask (11 bits here, up to 53 stay exact); the epsilon-closure of each move is an OR of per-state closure masks; accept is one AND (verified 1270 ACCEPT for aabb, 758 REJECT for ab). It is Shift-Or’s (119) machinery on an NFA instead of a pattern. Note:building the NFA from an arbitrary regex wants a node structure (the string want + a node arena, PS-015); the transition/closure tables here are precomputed f64 arrays. The demo simulates the exact 11-state NFA; the compiler grounds the bitmask walk.