Python - find（）函数的代价

Question

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

但是，我没有看到使用find（）那里。使用find（）函数会很昂贵吗？时间复杂度是多少？

我看过维基页面，但没有找到find（）。 https://wiki.python.org/moin/TimeComplexity

Answer 1

快速细读源，似乎str.find电话stringlib_find_slice从here最终调用fastsearch。实际的算法解释为here - 使用python伪代码（我从阅读注释中收集）。

它看起来像在最坏的情况下执行O（N * M）（与天真方法相同），但可以在某些情况下执行O（N/M）（其中N和M是字符串和子字符串）和O（N）在常见情况下。

^{（不要引用我 - 我只是掠过文件）}