diff options
| author | Dennis Sweeney <36520290+sweeneyde@users.noreply.github.com> | 2021-02-28 18:20:50 (GMT) |
|---|---|---|
| committer | GitHub <noreply@github.com> | 2021-02-28 18:20:50 (GMT) |
| commit | 73a85c4e1da42db28e3de57c868d24a089b8d277 (patch) | |
| tree | ed2b044a2b8bd42bb611922bbcacbaf3599e91f9 /Misc/NEWS.d | |
| parent | 2183d06bc8a481098d62a4ebed8d6982b3d1602a (diff) | |
| download | cpython-73a85c4e1da42db28e3de57c868d24a089b8d277.zip cpython-73a85c4e1da42db28e3de57c868d24a089b8d277.tar.gz cpython-73a85c4e1da42db28e3de57c868d24a089b8d277.tar.bz2 | |
bpo-41972: Use the two-way algorithm for string searching (GH-22904)
Implement an enhanced variant of Crochemore and Perrin's Two-Way string searching algorithm, which reduces worst-case time from quadratic (the product of the string and pattern lengths) to linear. This applies to forward searches (like``find``, ``index``, ``replace``); the algorithm for reverse searches (like ``rfind``) is not changed.
Co-authored-by: Tim Peters <tim.peters@gmail.com>
Diffstat (limited to 'Misc/NEWS.d')
| -rw-r--r-- | Misc/NEWS.d/next/Core and Builtins/2020-10-23-23-17-23.bpo-41972.kbAwg4.rst | 1 |
1 files changed, 1 insertions, 0 deletions
diff --git a/Misc/NEWS.d/next/Core and Builtins/2020-10-23-23-17-23.bpo-41972.kbAwg4.rst b/Misc/NEWS.d/next/Core and Builtins/2020-10-23-23-17-23.bpo-41972.kbAwg4.rst new file mode 100644 index 0000000..609a0ff --- /dev/null +++ b/Misc/NEWS.d/next/Core and Builtins/2020-10-23-23-17-23.bpo-41972.kbAwg4.rst @@ -0,0 +1 @@ +Substring search functions such as ``str1 in str2`` and ``str2.find(str1)`` now sometimes use the "Two-Way" string comparison algorithm to avoid quadratic behavior on long strings.
\ No newline at end of file |