[Bug libstdc++/85472] Regex match bug
haberg-1 at telia dot com
Wed May 2 21:48:00 GMT 2018
--- 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.
More information about the Gcc-bugs