[Bug libstdc++/85472] Regex match bug

[haberg-1 at telia dot com]

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

--- Comment #15 from Hans Åberg <haberg-1 at telia dot com> ---
(In reply to Tim Shen from comment #14)
> How fast does your prototype run on the following example?
>   ((10)|(11)|(12)|...|(98)|(99))* matching "10111213141516...9899"
> how about this:
>   ((100)|(101)|(102)|...|(998)|(999))* matching "100101102...998999"
> 
> where "..." are the skipped strings that follow the surrounding pattern.

My program does not choke on limit cases, like the regex '(a?)^k a^k' on the
string string "a"^k, mentioned at [1]; for k = 100, it takes 0.393 s on the NFA
and 0.168 on the DFA on a not so powerful computer. Otherwise, it is not
optimized and fast in absolute terms: I use standard C++ containers such as
unordered_set for DFA state lookups, and not a number.

1. https://swtch.com/~rsc/regexp/regexp1.html