从字符串中的一组单词中出现一个单词

Question

有人可能会建议使用该算法从字符串中的一组K单词中找到任何单词的出现次数吗？
例如：
单词集合：{ABC，XYZ}
字符串：ABC defghi ABC jklab XYZ
输出：{0,9,17} //开始在字的位置字符串

比运行KMP K次更好的东西！

Answer 1

Aho-Corasick algorithm旨在搜索文本中给定词典中的任何词。

有some other algorithms这个任务 - Commentz - 瓦尔特·拉宾 - 卡普（但阿霍 - Corasic一个具有更好的为最坏的情况复杂）

Answer 2

如果要在工业规模上执行此操作，请使用后缀树。您将每个后缀存储在字符串中，然后您可以基本上在O常量时间内搜索子字符串，因为所有子字符串都是具有不同后缀的相同字符串。

但是，在后缀树证明复杂性的前提下，它们需要很长的时间（它们在现实中用于扫描DNA序列数据等）。