two-way for `str.rfind`

Feature or enhancement

Proposal:

After closing with: https://github.com/python/cpython/pull/120025#issuecomment-5281829097

I appreciate that str.rfind is much less frequently used than str.find. But as can be seen it the PR above, it is fairly easy to make two_way bi-directional to handle both. I concluded that for standard track Horspool algorithm the cost of bi-directional logic is best avoided - those methods are fairly short and simple. However, two-way is a plausible candidate I think. Having separate functions for both direction would mean very large code duplications and I think paying a small perf cost to keep single logic for both might be a fairly good deal.

I think it would be good to do it - single string search is one of the most important low level algorithms - having this space clean and complete is I think a good thing -- it would give peace of mind for developers and predictable behaviour for users, and library developers who make heavy use of string search, allowing to derive new algorithms that work in both directions without performance surprises when running in reverse.

There is a workaround of course:

idx = str[::-1].find(sub[::-1])
if idx != -1:
    idx = len(str) - len(sub) - idx

However, for small problem sizes this is a non-trivial overhead + double memory.

So, what are the thoughts of others?
Is adapting two-way search to serve str.rfind (eliminating its O(n^2) worst case) desirable/worthwhile?

cc @methane @rhettinger @serhiy-storchaka @vstinner

Has this already been discussed elsewhere?

No response given

Links to previous discussion of this feature:

No response

Beginnen Sie mit dem str.rfind-Einstiegspunkt und der bestehenden two_way-Suchlogik, die im verlinkten Pull Request besprochen wird. Vergleichen Sie die Anforderungen an die Vorwärts- und Rückwärtssuche und bewerten Sie anschließend, ob eine bidirektionale Verarbeitung den Worst Case O(n^2) von str.rfind ohne inakzeptable Leistungseinbußen oder duplizierte Funktionen vermeiden kann. Als abgeschlossen gilt die Aufgabe, wenn das Design abgestimmt ist und sein Verhalten sowie seine Abwägungen validiert sind.