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

  • Z时代
  • 2024-01-10
  • 分类：问答

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

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

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

回答：

它是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（σ）依赖性）

  • 许多现实生活中的搜索应该是好的，很少是最坏的情况

  • 相当简单的实现

以上是 Python字符串'in'运算符实现算法和时间复杂度 的全部内容， 来源链接： utcz.com/qa/429292.html

回到顶部