我用下面的字母表生成了一个字符串。{A,C,G,T}。我的字符串包含10000多个字符。我在里面搜索以下模式。
阿特加
TGGAC公司
循环燃气轮机
我要求使用一个运行时间O(m+n)的字符串匹配算法。
m = pattern length
n = text length
两者都有这个运行时间。在这种情况下（rabin-carp和kmp之间）最合适的算法是什么？
最佳答案
当您想要搜索多个模式时，通常正确的选择是使用Aho-Corasick，这在某种程度上是KMP的泛化。现在在您的例子中，您只搜索3个模式，因此可能KMP没有那么慢（最多3次），但这是一般的方法。
Rabin-Karp如果我们假设永远不会发生冲突，则更容易实现，但如果您遇到的问题是典型的字符串搜索，那么不管您有什么输入，kmp都会更稳定。然而，rabin-karp还有许多其他应用，其中kmp不是一个选项。