Fix consumed character tracking in Jaro-Winkler matching - #15483

Describe your change

• Add an algorithm?
• Fix a bug or typo in an existing algorithm?
• Add or change doctests? -- Added at the maintainer's explicit request; all existing tests are preserved.
• Documentation change?

Track consumed target indices in jaro_winkler instead of replacing matched characters with spaces. A literal space can currently match those replacement characters: jaro_winkler("aa ", "aa") returns 1.1333333333333333 and jaro_winkler("a a", "aa") returns 1.15, exceeding the documented range.

The matching loop now consumes the actual unused position inside the existing window. This also avoids whole-string .index() selecting a repeated character before that window. Window size, score formulas, and all existing doctests are unchanged.

Validation under CPython 3.15.0rc2 free-threaded:

• All 11 doctest examples pass: the original 8 are unchanged, and 3 regression assertions were appended. All 3 new assertions fail against the original algorithm.
• Seven external regression/control cases pass.
• All 132,496 pairs of strings of lengths 0–5 over a, b, and space stay within [0, 1]; the original code has 3,034 out-of-range results.
• The same pairs preserve their score when space is consistently renamed to NUL; the original code has 44,542 violations.
• pre-commit run --all-files --show-diff-on-failure: passed.

The original external oracle results above remain applicable: this follow-up does not change the production function. In response to the maintainer's request, the same file now includes appended regression doctests and an optional benchmark. The “2k-item tree” wording is interpreted as approximately 2,000-character strings for this string algorithm.

Run:

python3.15t strings/jaro_winkler.py --benchmark

The exact same benchmark block was run with the original algorithm from 84b73d08 and the proposed implementation, using CPython 3.15.0rc2 free-threaded, GIL disabled, CPU 0 affinity, and the best of five single-call repetitions. Input construction and the displayed correctness score are outside the timer.

These measurements expose a material performance cost in the current correctness fix on these long inputs. The proposed index/set scan runs in Python, whereas the original uses C-level string operations; the original trailing-space result is incorrect and exceeds 1. These are workload-specific local measurements, not a performance improvement or a universal ratio. The performance tradeoff is reported for maintainer review; no optimization is silently included in this tests-and-benchmark follow-up.

This original change was prepared with AI assistance and independently reviewed. The follow-up independently preserves all original examples and production statements, proves the new regressions, and compares identical benchmark code.

Checklist

• I have read CONTRIBUTING.md.
• This pull request is all my own work -- I have not plagiarized. (Original change prepared with AI assistance, as disclosed above.)
• I know that pull requests will not be merged if they fail the automated tests.
• This PR only changes one algorithm file. To ease review, please open separate PRs for separate algorithms.
• All new Python files are placed inside an existing directory.
• All filenames are in all lowercase characters with no spaces or dashes.
• All functions and variable names follow Python naming conventions.
• All function parameters and return values are annotated with Python type hints.
• All functions have doctests that pass the automated testing.
• All new algorithms include at least one URL that points to Wikipedia or another similar explanation. (Not applicable: no new algorithm.)
• If this pull request resolves one or more open issues, then the description above includes the issue number(s) with a closing keyword: "Fixes #ISSUE-NUMBER". (Not applicable: no linked issue.)