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

当您想要搜索多种模式时，通常正确的选择是使用Aho-Corasick，这在某种程度上是KMP的概括。现在，在您的情况下，您只搜索 3 种模式，因此 KMP 可能并没有那么慢（最多三倍），但这是一般方法。

如果我们假设冲突永远不会发生，Rabin-Karp更容易实现，但如果您遇到的问题是典型的字符串搜索，那么无论您有什么输入，KMP 都会更加稳定。但是，Rabin-Karp 有许多其他应用程序，其中 KMP 不是一个选项。