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

Question

例如，我正在考虑in操作员如何实现

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

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

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(σ) 依赖项）
• 许多现实生活中的搜索应该是好的，极少数应该是最坏的情况
• 相当简单的实现