從字符串中的一組單詞中出現一個單詞

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序列數據等）。