我正在考虑in操作员如何实施
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(σ)依赖性) 许多现实生活中的搜索应该是好的,很少是最坏的情况 相当简单的实现
在设计新算法时,我使用了以下约束: