Re^4: Recursive sub-pattern spectacularly slow, what's wrong? (me, or just this use case, or a bug?)

Backtracking: When a regex engine encounters ambiguous patterns, it may try multiple paths to find a match. This can lead to exponential time complexity in the worst case, especially with nested quantifiers (e.g., .* followed by another .* ).
Nested Quantifiers: Patterns like (a|b)*c can cause super-linear behavior when matched against strings that contain many a s and b s, as the engine may explore all combinations of a and b before concluding that there is no match.
Long Input Strings: The longer the input string, the more pronounced the super-linear behavior can become, especially if the regex is poorly constructed.

I was curious what a "detected a super-linear match" means and asked Duck-AI. Explanation below. (LLMs are good in condensing knowledge as long as you review the output like I did. see also https://stackoverflow.com/questions/12841970/how-can-i-recognize-an-evil-regex)

Basically its trying to detect that the complexity is more ("super") than linear and turns on caching.

Since the situation from starting from "c" without prior match is the same like with a prior "b" or "ab" the cached result of a FAIL can be used to shortcut the search when starting from "c", "d" and so on.

Of course you could also apply the same mechanism with recursive regexes, but as I said the use cases are rare.

Cheers

- LanX (LogIn timing out again)

Comment on Re^4: Recursive sub-pattern spectacularly slow, what's wrong? (me, or just this use case, or a bug?) Select or Download Code