Martijn van Oosterhout <kleptog@svana.org> writes:
> On the otherhand, I think requiring an "overall longest match" makes
> your implementation non-polynomial complexity.
Only if you don't know how to implement it -- a DFA-based implementation
doesn't have much trouble with this.
> [ equivalence of knapsack problem to regexes with bounded repetition ]
Interesting, but note that neither the POSIX spec nor our implementation
permit arbitrarily large repetition counts, so the theoretical
NP-completeness is only theoretical.
> The question is, what are users expecting of the PostgreSQL regex
> implementation?
I think a minimum expectation is that we adhere to the POSIX
specification.
regards, tom lane