Many years ago, as a fresh out of college young coder, I had to come up with a way to check types on an text input file in C++ -- long before C++ had even a standard String type let alone regex libraries like pcre. The standard conversion functions at the time expected you to have done some type detection beforehand.

Each field in the file could contain a string, an int, or a float. In particular to figure out the floats, I remember sitting down for a few hours and coming up with a regular expression, testing it in Perl on a bunch of test cases, and then went about the hard work of slowly converting the regex into an NFA to a DFA and then finally to an adjacency graph in a 2d matrix. A little bit of code to read in things a byte at a time and some simple arithmetic and I had a stupid fast

   bool isFloat(char *)

Nobody at my work understood the code, they just sort of knew that if they submitted a character array with a field value into it, something happened with a big matrix, and it you let them know if it was a float or not and then they could call the appropriate conversion function -- I think stof() or whatever was in fashion back then.

I had to make one revision to it for an edge case I missed and then it found its way into pretty much all code for the company after that.

The tuition for the class that taught me how to do that payed for itself with that one function.

And if you don't have a cursory understanding of NFAs and DFAs, they're still great for getting that cursory understanding.

These articles were my introduction to finite automata (and almost the only place I've learned about them aside from practical use) and my intuition for them seem to often be better than my peers'.

You may also find this very detailed post interesting https://devblogs.microsoft.com/dotnet/regular-expression-imp...

It's an indepth look at where regex in dotnet was prior to and after version 7.

There's a fun list of problems like this here: https://cstheory.stackexchange.com/questions/6660/polynomial...

On the other hand, it's remarkable that so many algorithms _do_ have reasonable constants/exponents. So the concept works pretty well.

And the converse as well -- an algorithm that is 10,000,000 * n^17 is going to be effectively intractable but falls neatly into P.

And the reality is that most NP-complete problems are well-solved by heuristics except in strange combinatorial corners. It's why we can't just create encryption systems based on knowing the correct answer to an NP-complete problem; most of the problem instances will be too easy to solve.

FWIW, it seems pretty likely the same multi-NFA algorithm described in the article could be applied to other backtracking scenarios (and therefore to back references and lookaround). Since I’m just speculating, I’ll hazard a guess that it would result in a meaningfully more complex implementation to derive each state machine, and potentially much slower (while still “linear” complexity).

Thanks! Macroexpanded:

Regular Expression Matching Can Be Simple and Fast (2007) - https://news.ycombinator.com/item?id=20310669 - June 2019 (33 comments)

Regular Expression Matching Can Be Simple and Fast (2007) - https://news.ycombinator.com/item?id=16341519 - Feb 2018 (20 comments)

Regular Expression Matching Can Be Simple and Fast (2007) - https://news.ycombinator.com/item?id=9374858 - April 2015 (16 comments)

Regular Expression Matching Can Be Simple And Fast [2007] - https://news.ycombinator.com/item?id=6593331 - Oct 2013 (1 comment)

Regular Expression Matching Can Be Simple And Fast - https://news.ycombinator.com/item?id=820201 - Sept 2009 (15 comments)

Regular Expression Matching Can Be Simple And Fast - https://news.ycombinator.com/item?id=466845 - Feb 2009 (17 comments)

The GP doesn't really provide enough details to tell the difference between 1) the programmer did something wrong, or 2) the regex engine is missing optimizations or 3) the GP has a use case that is actually difficult to optimize for in the generality of the regex engine. Any one of these 3 things could be true. It's possible more than one is true simultaneously!

> a linear find should be equivalent to a well implemented regex search for a specific string of characters

This is only true theoretically. If your regex engine is just a DFA scan that does char-at-a-time matching, then any "well implemented" substring search algorithm is going to blow it out of the water because it likely uses SIMD. Of course, many regex engines (including RE2), detect literals in the regex and use SIMD to scan for it. So while "DFA scan that does char-a-time matching" is a fine semantic model to have (to a first approximation) for a finite automata based regex engine, the model breaks down pretty quickly for reasoning about performance in general.

Depending on the type of string search this is not completely true. A naive string search is O(kn) (where k is the length of the search string) which is actually slower than the O(n) that a DFA can get.

But KMP and similar algorithms can do better; they can get performance approaching O(n/k) for many cases by not even looking at every character of the input string.

It’s re2…