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

我使用以下字母生成了一个字符串。{A,C,G,T}。我的字符串包含超过 10000 个字符。我正在其中搜索以下模式。

• ATGGA
• TGGAC
• CCGT

我要求使用字符串匹配算法O(m+n)运行时间。

m = pattern length
n = text length

Both KMP and Rabin-Karp algorithms有这个运行时间。在这种情况下最合适的算法是什么（Rabin-Karp 和 KMP 之间）？

当您想要搜索多个模式时，通常正确的选择是使用阿霍-科拉西克 http://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_string_matching_algorithm，这在某种程度上是一个概括KMP https://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm。现在，在您的情况下，您只搜索 3 种模式，因此 KMP 可能不会慢很多（最多三倍），但这是一般方法。

拉宾-卡普 https://en.wikipedia.org/wiki/Rabin%E2%80%93Karp_algorithm如果我们假设永远不会发生冲突，则更容易实现，但如果您遇到的问题是典型的字符串搜索，则无论您有什么输入，KMP 都会更加稳定。然而，Rabin-Karp 还有许多其他应用，而 KMP 则不适用。