文本掃描，檢查是否包含從指定列表

Question

要求

1. 詞目前我們有一個包含超過一萬個關鍵字或句子（數爲N）
2. 輸入很長的字符串列表，長度爲L

問題：檢查字符串是否包含可以被描述爲w給出

的問題列表中的關鍵詞或句子ord篩選wikipedia，但我沒有在該頁面上找到任何算法。解決這個問題最簡單的方法是迭代所有關鍵字或句子，每次檢查長文本是否包含這樣的子字符串。由於我們有很多關鍵字，也考慮到長文本，所以表現非常糟糕。它使用O（NL）時間

似乎應該在O（L）中完成更好的解決方案。任何人都可以對此提出一些建議嗎？

Answer 1

有幾種方法解決這個問題具有時間複雜度O（M + L），其中L是字符串的長度和M被組合的所有模式的長度：

1. Aho–Corasick string matching algorithm。
2. 使用Ukkonen's algorithm爲字符串構造一個suffix tree，然後爲每個模式找到該後綴樹的匹配項。
3. 爲模式集合構造一個generalized suffix tree，然後找到輸入字符串和該後綴樹之間的匹配。
4. 構造一個Suffix array作爲字符串，並用它來搜索每個模式。這種方法的時間複雜度爲O（M + L + N log L），其中N是模式的數量。
5. Commentz-Walter algorithm。

你可以在這本書中找到所有這些算法的細節（除了Commentz-Walter算法）：Algorithms on Strings, Trees and Sequences by Dan Gusfield。

---

如果您可以明確地從輸入字符串中提取單獨的單詞/句子，則可以使用幾種不同的（更簡單的）方法。

1. 準備一個大小足夠大的Bloom filter以保證N個模式的誤報概率較低。添加到Bloom過濾器位，由關鍵字/句子的散列函數確定。然後掃描字符串，提取連續的單詞/句子，並檢查這些單詞/句子是否可以在Bloom過濾器中找到。只有在Bloom過濾器中存在單詞/句子時，纔可以在模式列表中搜索它。該算法具有期望的時間複雜度O（M + L）並且節省空間。
2. 將所有模式插入散列集。然後掃描字符串，提取連續的單詞/句子，並檢查它們中的任何一個是否在哈希集合中。這具有相同的期望時間複雜度O（M + L），比布魯姆過濾器方法簡單，但是不具有空間效率。
3. 將所有模式插入基數樹（trie）。然後用它從字符串中搜索單詞/句子。這與廣義後綴樹方法並無太大區別，但更簡單，性能更好。它具有最壞情況下的時間複雜度O（M + L），可能比布隆過濾器或散列集方法稍慢，並且如果需要可以使其非常節省空間。