字符串搜索算法

Question

对于两种字符串搜索算法：KMP 和后缀树，哪种算法在哪些情况下更受欢迎？请提供一些实际例子。

- avd

---

你自己觉得呢？现在看起来好像你只是抄袭了作业的一部分。 - Bart Kiers

这不是作业。我是一名在公司工作的专业程序员。这个问题只是为了获取知识。 - avd

如果你了解算法并知道它们的工作原理，那么构建一些示例来展示特定算法需要大量步骤的情况和快速情况应该不太难...（我记得曾经构建过一个仅由0和1组成的示例字符串，其中KMP需要执行所有步骤才能成功。） - phimuemue

@avd，如果这不是作业的话，你的问题表述有些别扭。 - Bart Kiers

非常有趣，AVD。你是一个实习生，将在六月份毕业。 - Svante

Answer 1

如果你需要频繁地回答类似于“指定字符串是否在目标字符串中”的问题，那么后缀树是更好的选择。如果你只需要在一个单一字符串中搜索一个字符串，且不需要多次执行此操作，那么KMP算法更加适合。

后缀树是一种更为通用的数据结构，因此可以实现更多的功能。你可以在这里查看它的更多应用。KMP算法则适用于判断一个字符串是否为另一个字符串的子串。

你也可以尝试其他算法，例如Boyer-Moore、Rabin-Karp以及朴素算法，因为在某些情况下其中一个算法可能会更加优秀。

总之：

1. 如果你有很多像上述问题一样的查询，则值得构建后缀树，以便更快地回答每个查询。
2. 如果你需要执行更多种类型的查询，那么构建后缀树也是值得的。
3. 如果你只关心偶尔找到一个字符串是否为另一个字符串的子串，那么使用KMP算法即可。

- IVlad