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

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

它是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位Unipre字符串都应该很好地工作（没有O（σ）依赖性）
• 许多现实生活中的搜索应该是好的，很少是最坏的情况
• 相当简单的实现