At search time, the principle difference between an NFA and a DFA is that, in an NFA, you can be in more than one state at the same time. There's no problem with implementing your transition function to advance all states you are in simultaneously for each character of input. You'll get `O(m * n)` time, where `m` is proportional to the number of states in the NFA and `n` is proportional to the length of the input.

The GP is remarking on a confusable term, "NFA algorithm," that has come to mean something different from its underlying theory. The PCRE2 documentation itself, for example[1], remarks about how it uses the "NFA algorithm" as its standard approach to matching. But of course, PCRE2 supports way more than the theoretical model of non-deterministic finite automata (NFA) actually supports. PCRE2 is much more expressive. Yet, the implementation approach is still called "NFA algorithm." Presumably the reason for this is that an NFA can be simulated by doing backtracking, but if you don't keep track of where you've visited, the worst case runtime of this is superlinear, possibly catastrophically so[2]. The problem is that the backtracking regex engines have evolved well beyond what an NFA actually supports. But the name stuck.

To make things even more confusing, as I mentioned above, an NFA can be used to execute a search in O(m * n) time. (We typically call that "linear in the size of the input" since the NFA itself can usually, but not always, be regarded as a constant factor. i.e., A literal regex string in your program source code.) So when you say something like, "a finite automata regex engine uses NFAs to guarantee linear time," you might be really confused if your background is in backtracking engines which... also use an "NFA," but of course cannot guarantee linear search time.

So what we have is ambiguous terminology, not unlike "regex" itself, which could perhaps mean a real theoretical "regular expression" (in the case of Hyperscan, RE2, Go's regexp package and Rust's regex crate) or it could mean "a very expressive DSL for pattern matching that supports more than what regular languages can describe" (in the case of PCRE2, ECMAScript's regex engine, Ruby's Oniguruma, Python's `re` module, and more). I've made my peace with "regex" being ambiguous, but the fact that "NFA algorithm" is itself ambiguous despite "non-deterministic finite automata" being a somewhat baroque and specific technical term, is very unfortunate.

To make things even worse---and I shit you not, I am not joking---the backtracking people seem to have taken to calling a linear time NFA search the "DFA algorithm."[3] (At least the PCRE2 docs mention it's not a "traditional" finite state machine...) But... it's not a DFA. The backtracking folks have effectively elevated the terms "NFA" and "DFA" to mean something very different from their theoretical underpinnings.

So when you have people that are only aware of one meaning of "NFA algorithm" talking to other people only aware of the other meaning of "NFA algorithm," chaos ensues.

[1]: https://www.pcre.org/current/doc/html/pcre2matching.html

[2]: https://github.com/BurntSushi/rebar?tab=readme-ov-file#cloud...

[3]: https://www.pcre.org/current/doc/html/pcre2matching.html#TOC...