Python - find() 函数的成本

Question

我正在寻找一种有效的方法来检查短字符串是否在长字符串中。我在这个线程上看到了一些建议： Python effective way to check if very large string contains a substring

但是，我在那里没有看到 find() 的用法。使用 find() 函数是否昂贵？时间复杂度是多少？

我查看了 Wiki 页面，但没有找到 find() 。 https://wiki.python.org/moin/TimeComplexity

Answer 1

快速浏览源代码，似乎从这里 str.find调用，最终调用. 实际的算法在这里用 python 伪代码（我从阅读评论中收集到）进行了解释。stringlib_find_slicefastsearch

看起来最坏情况下的实现是 O(N*M) （与简单的方法相同），但在某些情况下可以做到 O(N/M) （其中 N 和 M 分别是字符串和子字符串的长度)，在常见情况下为 O(N) ¹。

^{¹（不要引用我的话——我只是浏览了一下文档）}