KMP v.s.子字符串匹配的后缀树

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

在此先感谢，林

2015-12-03 Lin Ma

你能清楚地描述你的问题吗？什么是数据范围？什么样的查询？ – throwit

@ F.Ju，我需要找到一个字符串是否是另一个字符串的子字符串。例如，“ello”是“hello”的子字符串。期待您的建议。 :) –

如果你只有两个字符串我觉得KMP足够了 – throwit

运行时间和内存的复杂性是差不多的。您可以在O（N）中准备模式，并且可以在O（M）（您的字符串的长度）中进行搜索。

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

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

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

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

2015-12-03 10:30:08 Sorin

感谢Sorin，很好的回答，你能否再提一点建议你是什么意思“后缀树可以做更多的操作，而这些操作对你的应用来说可能不是必需的”？谢谢。 –

另一个快速的问题，你的意见，“你在O（N）准备模式，你可以搜索O（M）（你的字符串的长度）”，N是模式的长度，M是长度源字符串的？谢谢。 –

通过后缀树，您可以找到子串重复（xabcyzabcq - > abc * 2）或回文序列（xyzabcdcbaxyz - > abcdcba）。维基百科有一个很好的总结。 – Sorin

回答