https://gcc.gnu.org/bugzilla/show_bug.cgi?id=79539
Bug ID: 79539 Summary: <regex> __polynomial mode lookahead still has an exponential behavior Product: gcc Version: 7.0.1 Status: UNCONFIRMED Severity: normal Priority: P3 Component: libstdc++ Assignee: unassigned at gcc dot gnu.org Reporter: timshen at gcc dot gnu.org Target Milestone: --- Lookahead is implemented in terms of non-memoized recursion, which may have exponential behavior. In __polynomial mode, we can add a quadratic memoization to it, making it O(|state| * |target string|) at worst. It's not linear, but still polynomial.