> They operate completely differently (a regular automation vs. a stack based pattern matcher). It's more exciting than this actually! An implementation of for

> They operate completely differently (a regular automation vs. a stack based pattern matcher). It's more exciting than this actually! An implementation of formal regexes doesn't have to simulate an automaton explicitly. In fact, it can also use backtracking and keep its linear running time. Such an implementation would use an explicit stack and also keeps track of each state that has been visited for a particular position in the search text. If a state has already been visited, then it doesn't repeat itself. A backtracking implementation can be faster than a full NFA simulation if: 1) you need to track submatch boundaries, 2) you have a small regex and 3) you have small input. (2) and (3) are necessary because of the memory required to keep track of the states you've visited (proportional to len(regex) * len(search text)). (1) is necessary because you could otherwise use a DFA, which AFAIK, does not typically track submatch boundaries. Tracking submatch boundaries in a backtracking implementation is faster than simulating an NFA automaton because you only need to keep one copy of the capture locations around at any point in time. The NFA simulation has to copy them around a lot. (Of the regex implementations that guarantee linear running time, C++'s RE2, Go's `regexp` and now Rust's `regex` all implement a bounded backtracking algorithm... among others!)