“在'符实现算法的时间复杂度Python字符串

问题描述

我想到的在运营商如何实现，比如

I am thinking of how the in operator implement, for instance

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

在CPython中，该算法用于实现字符串匹配，什么是时间复杂度？有没有这方面有任何正式的文件或维基？

In CPython, which algorithm is used to implement the string match, and what is the time complexity? Is there any official document or wiki about this?

推荐答案

这是博耶 - 穆尔的组合和 Horspool 。

您可以在这里查看C code ：

You can view the C code here:

快速搜索/计数实现的基础上，博耶 - 穆尔和Horspool之间的混合，在顶部多了一些花俏。对于一些更多的背景信息，请参阅： http://effbot.org/zone/stringlib.htm

从上面的链接：

在设计新的算法，我用了以下的限制：

  
• 应比目前的蛮力算法对所有测试案例（根据真实生活中的code），其中包括吉姆Hugunin的最坏情况下的测试速度更快
  
• 在小设置的开销;没有动态分配的快速路径（O（米）的速度，O（1）用于存储）
  
• 在良好的情况下，次线性搜索行为（O（N / M））
  
• 不亚于目前的算法在最坏的情况更糟糕（O（NM））
  
• 应该工作以及8位字符串和16位或32位的Uni code字符串（无O（σ）的依赖）
  
• 在许多现实生活中的搜索应该是不错的，很少应该是最坏的情况下  相当简单的执行
  

• should be faster than the current brute-force algorithm for all test cases (based on real-life code), including Jim Hugunin’s worst-case test
• small setup overhead; no dynamic allocation in the fast path (O(m) for speed, O(1) for storage)
• sublinear search behaviour in good cases (O(n/m))
• no worse than the current algorithm in worst case (O(nm))
• should work well for both 8-bit strings and 16-bit or 32-bit Unicode strings (no O(σ) dependencies)
• many real-life searches should be good, very few should be worst case reasonably simple implementation

这篇关于“在'符实现算法的时间复杂度Python字符串的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！