https://gcc.gnu.org/bugzilla/show_bug.cgi?id=85472
--- Comment #14 from Tim Shen <timshen at gcc dot gnu.org> --- 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. For the record, for the 100-999 case, libstdc++ takes 0.112 seconds given a proper stack limit. libc++ takes 6.386 seconds. I have a C++ test case for this: #include <regex> #include <string> #include <iostream> constexpr int kStart = 100; constexpr int kEnd = 1000; int main() { std::regex re; { std::string re_string; re_string += '('; re_string += std::string("(") + std::to_string(kStart) + ")"; for (int i = kStart + 1; i < kEnd; i++) { re_string += '|'; re_string += '('; re_string += std::to_string(i); re_string += ')'; } re_string += ')'; re_string += '*'; re.assign(re_string); } std::string s; for (int i = kStart; i < kEnd; i++) { s += std::to_string(i); } std::smatch m; std::cout << std::regex_match(s, m, re) << "\n"; for (const auto p : m) { std::cout << p << " "; } std::cout << "\n"; return 0; }