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

从链接的 pull request 中讨论的 str.rfind 入口点和现有 two_way 搜索逻辑开始。比较正向搜索和反向搜索的要求，然后评估双向处理是否可以在不产生不可接受的性能成本或重复函数的情况下，避免 str.rfind 的 O(n^2) 最坏情况。设计达成一致，且其行为和权衡经过验证后，即视为完成。