On Wed, Oct 14, 2020 at 7:45 PM Steven D'Aprano <steve@pearwood.info> wrote:
Perhaps this is a silly suggestion, but could we offer this as an
external function in the stdlib rather than a string method?

That feels unworkable to me. 

For one thing, the 'in' operator hits this same issue, doesn't it? But for another, the example initially posted where the current code did or didn't hit that quadratic breakdown was just one extra character in a long string.  I cannot imagine end users knowing in advance whether their exact search will hit that unlucky circumstance that is very data dependent.

If it was a case of "in certain circumstances, this other function might be twice as fast" I can see that being useful.  But here we get a big-O explosion that went from milliseconds to hours on ostensibly similar operations.
That said, I do recognize that the `re` module also has pathological cases, and the standard library documentation explicitly says "maybe you want to try the third-party `regex` implementation."  That is sort of precedent for this approach.

The dead increasingly dominate and strangle both the living and the
not-yet born.  Vampiric capital and undead corporate persons abuse
the lives and control the thoughts of homo faber. Ideas, once born,
become abortifacients against new conceptions.