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

Start with the str.rfind entry point and the existing two_way search logic discussed in the linked pull request. Compare the forward and reverse search requirements, then evaluate whether bidirectional handling can avoid str.rfind's O(n^2) worst case without unacceptable performance cost or duplicated functions. Done means the design is agreed and its behavior and trade-offs are validated.