[Bug libstdc++/79539] New: __polynomial mode lookahead still has an exponential behavior

[timshen at gcc dot gnu.org]

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.