什麼時候可以使用KMP算法？

據我所知，KMP算法依賴於幫助程序數組，其中有前綴類似於後綴。當上述條件未滿足時，它將無法有效，因爲在幫助程序數組中包含全零。運行時會是O（m + n）嗎？如果我是對的，在這種情況下什麼是更好的子串算法？什麼時候可以使用KMP算法？

2017-02-22 Jun

要理解KMP何時是一個很好的算法，通常可以提出問題「有什麼選擇？」。

KMP有一個很好的優勢，它可以保證最差的效率。預處理時間總是O（n），搜索時間總是O（m）。沒有最壞情況的輸入，沒有發生不幸的可能性等等。如果你在真正巨大的字符串（大m）內搜索非常長的字符串（大n），與其他算法相比，這可能是非常可取的天真的（在不好的情況下可能需要時間Θ（mn）），Rabin-Karp（病理輸入可能需要時間Θ（mn））或Boyer-Moore（最壞情況可能是Θ（mn））。你說得對，KMP可能並不是所有必要的情況下，在字符串沒有太多重疊部分的情況下，但是你永遠不必擔心是否存在不好的情況，這絕對是一件好事！

KMP還具有處理可以一次完成的好處。如果你知道你要搜索相同的子字符串很多次，你可以做一次O（n）預處理工作，然後有能力搜索任何長度爲m的字符串，你想在時間O （M）。

來源

2017-03-01 22:52:28 templatetypedef

爲什麼會出現這種情況：沒有最壞情況的輸入，不可能發生不幸？當模式字符串中沒有重複模式時，幫助程序數組將包含所有的零，這意味着，在字符串的每個字符處，我們必須返回到模式字符串的開頭？ – Jun

@Jun回退數組將全部爲零，並且在每次不匹配時，我們都必須返回到模式字符串的開頭。但是，當發生這種情況時，我們還會在輸入字符串中向前推進相應的距離。輸入的每個字符最多隻能被讀取兩次。 – templatetypedef

恩，我現在明白了！謝謝！ – Jun

什麼時候可以使用KMP算法？

回答

相關問題