String search improvements

[dg-pb]

I have done some work on fastsearch.h module.

python/cpython#120025

PR was reviewed by few non-core-dev members and was subject to sufficient amount of iterations so that it is currently in stable state.

I have posted in coredev discourse, but without much luck.

So I thought maybe this is a better place to get some attention given that this is largely related to performance.

Apart from performance improvements, it does introduce consistency and simplifications that are helpful to move forward with further improvements (see String Search Overview, Coverage and API).

[markshannon]

It looks a worthwhile improvement, but I don't think anyone in our team is an expert enough in string searching algorithms to review it.

Trying pinging discourse again?

[iritkatriel]

CC @gsbrodal (an expert on string algorithms).

[dg-pb]

This is still hanging. And it is a blocker to further progress in this direction.

Just want to note, that to review this, knowledge of string search algorithms is not necessary.

The logic of complex linear time "two-way" algorithm has not been changed, so review is on:

1. making sure that changes did not alter previous logic of two-way find (no need to understand search algorithms)
2. making sure that direction agonistic logic has been implemented correctly (no need to understand search algorithms)
3. reviewing new main search function:
   a) fairly simple string search with couple of basic additional rules
   b) logic of falling back to more complex two-way search

Only 3a needs a bit of of understanding of string search logic (but not the complex linear time "two-way"), the rest can be done without it.

So although there is definitely a bit of work to review, but for someone with good C knowledge, it might not be as much as it might seem.