对于两种字符串搜索算法：KMP和后缀树，在什么情况下优选哪种？举一些实际的例子。
如果您必须回答很多查询，例如“大海捞针是否存在？”，则后缀树会更好。如果您只需在另一个字符串中搜索一个字符串，而不需要执行很多次，那么 KMP 会更好。
后缀树是一种更通用的数据结构，因此您可以用它做更多的事情。看看你能用它做什么here http://en.wikipedia.org/wiki/Suffix_tree。 KMP 对于查找一个字符串是否是另一个字符串中的子字符串非常有用。
您可能还想查看其他算法，例如博耶-摩尔 http://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm, 拉宾-卡普 http://en.wikipedia.org/wiki/Rabin%E2%80%93Karp_string_search_algorithm甚至是朴素的算法，因为在某些情况（输入）中，一个算法比其他算法更好。
底线是：
- 如果您有很多像我上面提到的那样的查询，那么值得构建一棵后缀树，然后更快地回答每个查询。
- 如果您需要做的不仅仅是这些类型的查询，那么后缀树也值得构建。
- 如果您只关心偶尔查找一个字符串是否是另一个字符串的子字符串，那么请使用 KMP。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
