algorithm - KMP 诉子串匹配的后缀树

Question

想知道是否有人可以提供一些关于选择 KMP 和后缀树之间的利弊的建议，如果我们想看看一个字符串是否是另一个字符串的子字符串？谢谢。

提前致谢，林

Answer 1

运行时和内存复杂度大致相同。您在 O(N) 中准备模式，然后您可以在 O(M) 中搜索(n，m 字符串长度)。

后缀树可以执行一些您的应用程序可能不需要的操作。

在 KMP 中，您准备一个搜索模式，然后您可以轻松地在多个字符串中查找它。

在后缀树中，您准备要搜索的文本，然后您可以轻松地在其中查找许多模式。尽管内存使用量是线性的，但常量很大，因此这将需要更多内存。

KMP 通常比后缀树更容易编码。