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

Bắt đầu với entry point str.rfind và logic tìm kiếm two_way hiện có được thảo luận trong pull request được liên kết. So sánh các yêu cầu của tìm kiếm xuôi và tìm kiếm ngược, sau đó đánh giá liệu việc xử lý hai chiều có thể tránh trường hợp xấu nhất O(n^2) của str.rfind mà không phải trả giá hiệu năng không thể chấp nhận hoặc tạo ra các hàm trùng lặp hay không. Công việc được xem là hoàn tất khi thiết kế đã được thống nhất và hành vi cùng các đánh đổi của nó đã được xác thực.