何时使用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）