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）在常見情況下。

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