用于子字符串匹配的 KMP 与后缀树

Question

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

提前致谢，林

Answer 1

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

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

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

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

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