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

Question

我正在考虑in运营商如何实施

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

在CPython中,哪个算法用于实现字符串匹配,以及时间复杂度是多少？有关于此的官方文件或维基吗？

Answer 1

这是Boyer-Moore和Horspool的结合.

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

快速搜索/计数实施,基于Boyer-Moore和Horspool之间的混合,顶部还有一些铃声和口哨声.有关更多背景信息,请参阅:http://effbot.org/zone/stringlib.htm.

从上面的链接:

在设计新算法时,我使用了以下约束:

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