algorithm - 字符串搜索算法

Question

对于两种字符串搜索算法：KMP 和后缀树，哪种情况下首选？举一些实际的例子。

Answer 1

如果您必须回答很多查询，例如“大海捞针是否存在？”，则后缀树会更好。如果您只需要在另一个字符串中搜索一个字符串，而不必多次这样做，那么 KMP 会更好。

后缀树是一种更通用的数据结构，因此您可以用它做更多的事情。看看你可以在这里做什么。KMP 对于查找一个字符串是否是另一个字符串中的子字符串很有用。

您可能还想查看其他算法，例如Boyer-Moore、Rabin-Karp甚至朴素算法，因为在某些情况（输入）中，其中一种算法优于其他算法。

底线是：

1. 如果您有很多像我上面提到的那样的查询，那么构建一个后缀树然后更快地回答每个查询是值得的。
2. 如果您需要做的不仅仅是这些类型的查询，那么后缀树也值得构建。
3. 如果您只关心偶尔查找一个字符串是否是另一个字符串的子字符串，请使用 KMP。