4 ms·
> Aside: out of curiosity it would have been interesting to see how a Thompson NFA[1] would have dealt with this. It wouldn't have dealt with it right? NFAs an
by hencq 11y ago
> Aside: out of curiosity it would have been interesting to see how a Thompson NFA[1] would have dealt with this.
It wouldn't have dealt with it right? NFAs and DFAs are equivalent and them being actually regular means they can't do things like count parentheses.
- zamalek 11y agoI miscommunicated the question: "how well would have a Thompson NFA have dealt with this?" I.e. How many magnitudes of order faster would it have been? If it was faster?
- joepvd 11y agoNFAs do not do backtracking. So the solution space would look different. More sane, and more performant, but it would not be a pure regex solution.