小编典典

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

algorithm

我正在考虑in操作员如何实施

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

在CPython中,使用哪种算法实现字符串匹配,时间复杂度是多少?是否有关于此的正式文件或维基?


阅读 931

收藏
2020-07-28

共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(σ)依赖性)
  • 许多现实生活中的搜索应该是好的,很少是最坏的情况
  • 相当简单的实现
2020-07-28