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

Iniziare dal punto di ingresso str.rfind e dalla logica di ricerca two_way esistente discussa nella pull request collegata. Confrontare i requisiti della ricerca in avanti e all’indietro, quindi valutare se la gestione bidirezionale possa evitare il caso peggiore O(n^2) di str.rfind senza un costo prestazionale inaccettabile o funzioni duplicate. Il lavoro si considera concluso quando il design è stato concordato e il suo comportamento e i relativi compromessi sono stati convalidati.