何時使用Rabin-Karp或KMP算法？

Question

我已經使用以下字母表生成了一個字符串。 {A,C,G,T}。而我的字符串包含超過10000個字符。我正在尋找下面的模式。

• ATGGA
• TGGAC
• CCGT

我已要求使用字符串匹配算法具有O(m+n)運行時間。

m = pattern length 
n = text length 

KMP and Rabin-Karp algorithms都有這個運行時間。在這種情況下什麼是最合適的算法（在Rabin-Carp和KMP之間）？

Answer 1

當你想搜索的多模式tipically正確的選擇是使用Aho-Corasick這是有點KMP的推廣。現在在你的情況下，你只是在尋找3種模式，所以KMP的速度可能不會太慢​​（最多三次），但這是一般的方法。

拉賓，卡普更容易實現，如果我們假設碰撞永遠不會發生，但如果你有這個問題是一個典型的字符串搜索KMP會更加穩定，無論你有什麼輸入。然而，拉賓卡普有許多其他應用程序，其中KMP不是一種選擇。

Answer 2

如果你想由於小集匹配（即DNA序列）最高的準確度，你需要使用海明距離算法。

（來源：https://arxiv.org/ftp/arxiv/papers/1401/1401.7416.pdf）