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

Question

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

我已经要求使用具有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不是一种选择.

在这种特殊情况下,您的字符串非常小,因此您可以计算完美的哈希值,避免冲突(稍微修改算法).因此,我认为这两种方法都有效.如果搜索模式可以变长,则这是不可能的.我的答案旨在解释类似问题的一般逻辑.对于这个问题,我认为两种方法都同样好.也许您可以对这两种解决方案进行基准测试并选择性能更好 (8认同)
@Tim Rabin Karp依赖于哈希函数的选择，无论您选择哪种函数，都会由于冲突而导致性能下降。KMP没有这个缺点，这就是我所说的“更稳定”的含义（也许这不是最适合在此上下文中使用的短语）。我已经使用Rabin-Karp解决了许多不同的问题，但是这里还有其他一些应用程序：它可以用于解决最大子回文问题（还有其他方法），我已经用它来找到重复的最长子字符串生成给定的输入字符串。 (2认同)