# Feature or enhancement

### Proposal:

Two-way algorithm currently does not incorporate *Horspool skip rule* when needle is periodic. As part of my work this led to difficulties in run-time predictions.

This rule is a significant determinant of run-time and a common factor of 2 algorithms. If this rule was implemented for periodic needles it might be achievable to predict runtimes and implement dynamic `adaptive_find`.

The image below shows different permutations of `string search inputs`. X-axis is of the format: `needle matching characters + needle non-matching characters`. And all cases are define so that they all have a window for 100K iterations. Actual runtimes and predicted.

Period circled in red is where periodic needles are constructed, all of the other periods construct non-periodic periods.

The default algorithm always uses *Horspool skip rule* and its addition to `two-way` algorithm makes both algorithms consistent and comparable.

![image](https://github.com/python/cpython/assets/3577712/3a8b0e20-b667-4d38-9d2d-60adaa2cf71f)

Below are run-times for 3 points - 1 from period circled in red and one from each nearby period at the same points within periods.
```python
# Adjacent period
nd = '_' * 3 + '1' * 10 + '_'
hs = '_' * (100_000 + 5)
%timeit hs.find(nd)    # 36.3 µs
# Target Period
nd = '_' + '1' * 10 + '_'
hs = '_' * (100_000 + 3)
%timeit hs.find(nd)    # 388 µs
# Adjacent period on the other side
nd = '1' * 10 + '_'
hs = '_' * (100_000 + 2)
%timeit hs.find(nd)    # 36.7 µs
```

Here is an example of absence of the rule:
```
>>> '_111_' in '_____________'
###### Finding "_111_" in "_____________".
split: "_" + "111_"
===== Two-way: "_111_" in "_____________". =====
Needle is periodic.
> "_____________"
> "_111_"
Right half does not match.
> "_____________"
>  "_111_"
Right half does not match.
> "_____________"
>   "_111_"
Right half does not match.
> "_____________"
>    "_111_"
Right half does not match.
> "_____________"
>     "_111_"
Right half does not match.
> "_____________"
>      "_111_"
Right half does not match.
> "_____________"
>       "_111_"
Right half does not match.
> "_____________"
>        "_111_"
Right half does not match.
> "_____________"
>         "_111_"
```

Finally, same plot after inclusion of the rule for periodic needles:

<img width="736" alt="Screenshot 2024-05-31 at 22 06 44" src="https://github.com/python/cpython/assets/3577712/e104d262-fd48-4689-9537-5ee46cae749b">

### Has this already been discussed elsewhere?

This is a minor feature, which does not need previous discussion elsewhere

### Links to previous discussion of this feature:

There was no discussion on this particular issue, but this is one of the building blocks to achieve:
https://discuss.python.org/t/optimize-str-find-aka-fastsearch/54483/12

<!-- gh-linked-prs -->
### Linked PRs
* gh-119880
<!-- /gh-linked-prs -->

Utilize last character gap for two-way periodic needles
This is a GitHub Issue
repo:cpython
owner:python
Title : Utilize last character gap for two-way periodic needles
Issue date:

--- start body ---
# Feature or enhancement

### Proposal:

Two-way algorithm currently does not incorporate *Horspool skip rule* when needle is periodic. As part of my work this led to difficulties in run-time predictions.

This rule is a significant determinant of run-time and a common factor of 2 algorithms. If this rule was implemented for periodic needles it might be achievable to predict runtimes and implement dynamic `adaptive_find`.

The image below shows different permutations of `string search inputs`. X-axis is of the format: `needle matching characters + needle non-matching characters`. And all cases are define so that they all have a window for 100K iterations. Actual runtimes and predicted.

Period circled in red is where periodic needles are constructed, all of the other periods construct non-periodic periods.

The default algorithm always uses *Horspool skip rule* and its addition to `two-way` algorithm makes both algorithms consistent and comparable.

![image](https://github.com/python/cpython/assets/3577712/3a8b0e20-b667-4d38-9d2d-60adaa2cf71f)

Below are run-times for 3 points - 1 from period circled in red and one from each nearby period at the same points within periods.
```python
# Adjacent period
nd = '_' * 3 + '1' * 10 + '_'
hs = '_' * (100_000 + 5)
%timeit hs.find(nd)    # 36.3 µs
# Target Period
nd = '_' + '1' * 10 + '_'
hs = '_' * (100_000 + 3)
%timeit hs.find(nd)    # 388 µs
# Adjacent period on the other side
nd = '1' * 10 + '_'
hs = '_' * (100_000 + 2)
%timeit hs.find(nd)    # 36.7 µs
```

Here is an example of absence of the rule:
```
>>> '_111_' in '_____________'
###### Finding "_111_" in "_____________".
split: "_" + "111_"
===== Two-way: "_111_" in "_____________". =====
Needle is periodic.
> "_____________"
> "_111_"
Right half does not match.
> "_____________"
>  "_111_"
Right half does not match.
> "_____________"
>   "_111_"
Right half does not match.
> "_____________"
>    "_111_"
Right half does not match.
> "_____________"
>     "_111_"
Right half does not match.
> "_____________"
>      "_111_"
Right half does not match.
> "_____________"
>       "_111_"
Right half does not match.
> "_____________"
>        "_111_"
Right half does not match.
> "_____________"
>         "_111_"
```

Finally, same plot after inclusion of the rule for periodic needles:

<img width="736" alt="Screenshot 2024-05-31 at 22 06 44" src="https://github.com/python/cpython/assets/3577712/e104d262-fd48-4689-9537-5ee46cae749b">

### Has this already been discussed elsewhere?

This is a minor feature, which does not need previous discussion elsewhere

### Links to previous discussion of this feature:

There was no discussion on this particular issue, but this is one of the building blocks to achieve:
https://discuss.python.org/t/optimize-str-find-aka-fastsearch/54483/12

<!-- gh-linked-prs -->
### Linked PRs
* gh-119880
<!-- /gh-linked-prs -->

--- end body ---
