> Well the Rust docs say "all searches execute in linear time with respect to the size of the regular expression and search text." Yeah, that's ambiguous phras

> Well the Rust docs say "all searches execute in linear time with respect to the size of the regular expression and search text." Yeah, that's ambiguous phrasing on my part. I meant that it was linear time with respect to both the size of the regex and the search text. > Their engine compiles to a DFA, not an NFA or PikeVM; I suppose this is the basis for their claim. No, it doesn't. rust/regex uses some combination of the Pike VM, (bounded) backtracking and a lazy DFA. It will compile a DFA ahead of time in some cases where Aho-Corasick can be used. > Rust compiles to a DFA that supports capture groups. No, it uses a lazy DFA to answer "where does it match," but it still must use either the Pike VM or the bounded backtracker to resolve capture groups. > My question is whether capture groups ruin the linearity of the DFA matching. Yeah I think I would probably look at Tagged DFAs to answer this. You'll want to check out recent papers that cite Laurikari's work, since I think there have been some developments!