[Bug libstdc++/85472] Regex match bug

[haberg-1 at telia dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=85472

--- Comment #22 from Hans Åberg <haberg-1 at telia dot com> ---
(In reply to Tim Shen from comment #16)
> ...I meant to observe whether the example triggers a O(k^2) behavior. It
> should be less than quadratic. ...

> Here is the updated example, to re-arrange the expression to a tree, not a
> chain of "|" operators.

The matching itself that I do is linear O(k): I used a version of your example
for my program, timing the part in question for various values, dividing with N
and N^2, where N is the difference of the input numbers, making it easy to see
if it is O(k) or O(k^2).

However, in your example, the DFA lexing is quadratic, probably because I use
unordered_set objects that here gets size proportional to N. Thus this ought to
be optimized. So you might check if that might be an issue in the C++ library.