我使用以下字母表生成了一个字符串。
{A、C、G、T}。而我的字符串包含超过 10000 个字符。我正在其中搜索以下模式。
- ATGGA
- TGGAC
- CCGT
我已经要求使用具有 O(m+n) 运行时间的字符串匹配算法。
m = pattern length
n = text length
KMP 和 Rabin-Karp 算法 都有这个运行时间。在这种情况下，最合适的算法(介于 Rabin-Carp 和 KMP 之间)是什么？
最佳答案
当您想搜索多个模式时，通常正确的选择是使用 Aho-Corasick ，这有点概括了 KMP .现在，在您的情况下，您只搜索 3 种模式，因此 KMP 可能不会慢很多(最多三倍)，但这是一般方法。
Rabin-Karp如果我们假设永远不会发生碰撞，则更容易实现，但如果您遇到的问题是典型的字符串搜索，则无论您有什么输入，KMP 都会更加稳定。然而，Rabin-Karp 还有许多其他应用，其中 KMP 不是一个选项。
关于string - 何时使用 Rabin-Karp 或 KMP 算法？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/23336807/