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

Question

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

• ATGGA
• TGGAC
• CCGT

我被要求使用一个具有O(m+n)运行时间的字符串匹配算法。

m = pattern length
n = text length

KMP算法和Rabin-Karp算法的运行时间都相同。在这种情况下，哪个算法（Rabin-Karp和KMP）最合适？

- Sukeshini

---

如果您已经实现了某些代码，无论是其中的任何一个或两个，您可能还想在codereview.stackexchange.com上发布此代码。 - shree.pat18

感谢您的快速回复。我已经开发出生成字符串的部分，但我想确认应该使用什么算法。只有这样，我才能继续开发。 - Sukeshini

Rabin-Karp算法的最坏时间复杂度为O(n*m)。 - Michael Foukarakis

你有没有想过使用Aho-Corasick算法？它非常接近你对于“O(m+n)”的要求，是匹配多个模式的好选择，并且易于并行化。 - Michael Foukarakis

@Michael Foukarakis：谢谢您的建议。但是我想要在这两个算法中选择一个。 - Sukeshini

Answer 1

如果你想搜索多个模式，通常使用的正确选择是Aho-Corasick，这有点是KMP的一般化。现在在你的情况下，你只搜索三个模式，所以KMP可能并不会慢太多（最多三倍），但这是一般的方法。

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

- Ivaylo Strandjev

---

在这种情况下，你的字符串非常小，因此你可以计算出完美哈希值，避免碰撞（通过轻微修改算法）。因此，我认为这两种方法都能够起作用。如果搜索模式变得更长，则不可能使用完美哈希。我的回答旨在解释类似问题的一般逻辑。对于这个问题，我认为这两种方法同样好。也许你可以对这两种解决方案进行基准测试并选择性能更好的一个？ - Ivaylo Strandjev

谢谢。"然而，Rabin-Karp有许多其他应用场景，其中KMP不是一个选项"中的应用场景是什么？"一个典型的字符串搜索KMP会更稳定"中的稳定是什么意思？ - Tim

@Tim Rabin-Karp算法的实现依赖于哈希函数的选择，无论使用哪种函数，由于哈希冲突的存在，都会导致性能降低。而KMP算法则没有这个缺点，这就是我所说的“更加稳定”的意思（也许这个短语在此情境下不太适用）。 我已经使用Rabin-Karp算法解决了许多不同的问题，以下是一些其他应用：它可以用来解决最大回文子串问题（还有其他方法），我已经用它来查找生成给定输入字符串的最长重复子字符串。 - Ivaylo Strandjev

@IvayloStrandjev 或其他人能否提供适用于 Rabin Karp 的场景或问题？ - Saheel Sapovadia

我已经将它用于很多不同的问题。例如，使用Rabin-Karp算法，您可以在O(n*log(n))的时间内计算最长回文子串（结合两个Rabin-Karp算法来处理两个方向并进行二分查找）。 - Ivaylo Strandjev