第3章 多樣式比對與索引#

單一樣式的比對已經有 KMP、Boyer-Moore 等優秀解法，但許多真實應用要同時處理成千上萬個樣式：敏感詞過濾需要一次掃描數萬個禁用詞；字典與自動更正需要快速查詢「某個詞開頭的字」；全文檢索需要對一篇文章回覆「任意子字串在哪裡出現」。為此，本章介紹將樣式集合建成索引結構的方法：先投入設定時間建構索引，之後每次查詢都很快。

3.1 節介紹 Trie（字典樹）：把每個樣式前綴都變成樹上節點，查詢成本只與「查詢字串長度」成正比，與字典大小無關；3.2 節介紹 Aho-Corasick 演算法——把 KMP 的失敗連結推廣到 Trie 上，實現一次掃描、同時比對全部樣式的 O(n + m) 線性演算法，這是敏感詞過濾的標準解；3.3 節介紹後綴陣列與後綴樹：整篇文章的所有後綴排序後形成的索引，可回答任意子字串的位置、最長重複子字串、最長共同子字串等深度問題。

學完本章，讀者應理解「索引」與「比對」的權衡：索引適合重複查詢的場景，一次比對適合偶發需求。