请问有人能就在查找一个字符串是否为另一个字符串的子字符串时选择KMP和后缀树之间的优缺点给一些建议吗？谢谢。
提前致谢， Lin
KMP算法与后缀树在子字符串匹配中的比较
5
- Lin Ma
4
1你能清楚地描述一下你的问题吗？数据范围是什么？查询类型是什么？ - throwit
@F.Ju，我需要找出一个字符串是否是另一个字符串的子串。例如，“ello”是“hello”的子串。期待您的建议。 :) - Lin Ma
1如果您只有两个字符串，我认为KMP就足够了。 - throwit
@F.Ju，为什么？欢迎提供更多细节。谢谢。 - Lin Ma
1个回答
8
运行时和内存复杂度大致相同。您可以在O（N）中准备模式，然后可以在O（M）（n，m为字符串长度）中进行搜索。
Suffix树可以执行一些可能不必要的操作，这对于您的应用程序可能并非必需。
在KMP中，您准备了一个搜索模式，然后可以轻松地在多个字符串中查找它。
在Suffix树中，您准备要搜索的文本，然后可以轻松地在其中查找许多模式。尽管使用的内存是线性的，但常数很大，因此需要更多的内存。
KMP通常比Suffix树更容易编写。
- Sorin
13
1使用后缀树，您可以找到子字符串重复（xabcyzabcq-> abc * 2）或回文序列（xyzabcdcbaxyz-> abcdcba）。维基百科对它们有一个很好的总结。 - Sorin
1@LinMa 对于KMP算法，您需要准备搜索模式，而对于后缀树，则需要准备搜索文本。在这两种情况下，操作的时间复杂度都是O(字符串长度)，而搜索的时间复杂度则是O(另一个字符串长度)。对于一次性操作（在一个大字符串中搜索一个模式），从复杂度的角度来看，选择其中一种并没有任何好处。它们都是线性的。 - Sorin
1@LinMa 是的，你可以为大文本构建后缀树以查找模式。要查找重复字符串，您可以选择任何节点（除了根节点），从根到您的节点的路径是重复的字符串。要查找重复次数，您需要计算从您选择的节点开始的子树中叶子节点的数量（每个叶子节点都是以相同字符开头的不同后缀）。至于回文算法，我不确定（迄今为止没有使用过），但我相信您可以在维基百科上找到建议。 - Sorin
1@LinMa 根节点是树的根（没有任何父节点的节点）。"你的节点"是对应于重复字符串的节点。对于abc，您需要找到对应于abc的节点（它可以是根节点以下的一个或多个链接）。从根到节点的路径编码了字符串abc。如果您查看子树，您将找到2个叶子节点，分别对应后缀abcyzabcq和abcq（在子树中，您只能找到yzabcq和q，因为前导的abc在我们谈论的子树之上）。 - Sorin
1几乎正确，你应该计算子树中的所有叶子节点，而不仅仅是直接子节点。 - Sorin
显示剩余8条评论
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接