Apparently I reinvented almost the same code several years after Pike:
https://github.com/redis/redis/blob/99ebbee2b260b3466672b4fa...
https://github.com/redis/redis/blob/99ebbee2b260b3466672b4fa...
Demo: https://tio.run/##tVddc6IwFH3nV0Q7WyXFIlrdUWr7uC/9B213BkIQKo...
pattern = "a*b*c*d*e*f*g*h*i*j*k*l*m*n*o*p*q*r*s*t*u*v*w*x*y*z"
text = "aabbccddeeffgghhiijjkkllmmnnooppqqrrssttuuvvwwxxyyzza"
running time = 1.6s
The repetition operator provokes the cliff because it represents short-hand syntax for easily increasing `m` to very large sizes. Indeed, by default, '.{12345}' will fail to compile because it blows the default limit. That only works because, as I said, the cliffs for finite automata based regex engines are far more predictable.
An NFA / DFA would be a perfectly valid way to implement an efficient matcher, but it's not the only way.
For example, memoization (https://news.ycombinator.com/item?id=32434412#32436442) can be easily shown to have time complexity O(P * T) where P = len(pattern) and T = len(text), which is the same as a basic NFA implementation.
In the case of the Redis code, my proposed fix requires much less code and memory than memoization or an NFA, and has time complexity O(P * T). It's slightly harder to prove this bound; here is a sketch of the proof:
Matching against a pattern fragment that does not contain "*" takes O(len(pattern_fragment)).
When a call to stringmatchlen() encounters a wildcard, it may recurse O(T) times (and then it returns). Each recursive call can be classified either "leaf" (if there is a match failure before the next wildcard) or "full" (if the match reaches the next wildcard).
The insight I described leads to at most one "full" call at each level of the recursion (i.e. for each wildcard in the pattern). So for a particular pattern fragment, the number of "leaf" calls that process it is O(T). Hence the overall time complexity is O(P * T).
Although its space complexity is P*T, which limits its use to small regexes/haystacks. It sounds like your claim is that your technique achieves a smaller space bound?