Python字符串'in'运算符实现算法及时间复杂度

Question

我正在考虑

in

运算符如何实现，例如

>>> s1 = 'abcdef'
>>> s2 = 'bcd'
>>> s2 in s1
True

在CPython中，使用哪种算法来实现字符串匹配，时间复杂度是多少？有没有相关的官方文档或wiki？

Answer 1

它是 Boyer-Moore 和 Horspool 的组合。

您可以在此处查看C代码：

快速搜索/计数实现，基于 Boyer-Moore 和 Horspool 之间的混合，并在顶部添加了一些附加功能。有关更多背景信息，请参阅：https://web.archive.org/web/20201107074620/http://effbot.org/zone/stringlib.htm.

来自上面的链接：

在设计新算法时，我使用了以下约束：

• 对于所有测试用例（基于现实代码）都应该比当前的暴力算法更快，包括 Jim Hugunin 的最坏情况测试
• 设置开销小；快速路径中没有动态分配（速度为 O(m)，存储为 O(1)）
• 良好情况下的次线性搜索行为 (O(n/m))
• 在最坏情况下不比当前算法差（O(nm)）
• 应该适用于 8 位字符串和 16 位或 32 位 Unicode 字符串（无 O(σ) 依赖性）
• 许多现实生活中的搜索应该是好的，很少应该是最坏的情况
• 实现相当简单

Answer 2

自 2021 年起，CPython 使用 Crochemore 和 Perrin 的双向算法来处理更大的 n。

来自

源代码：

如果琴弦足够长，请使用 Crochemore 和 Perrin 的双向 算法，其最坏情况的运行时间为 O(n)，最佳情况的运行时间为 O(n/k)。 还计算一个移位表以在更多情况下实现 O(n/k)， 并且通常（取决于数据）推断出比纯 C&P 更大的偏移 推断。请参阅此文件夹中的 stringlib_find_two_way_notes.txt 以获取 详细解释。

参见

https://github.com/python/cpython/pull/22904