字串處理#
字串匹配是程式設計中的基礎問題，從文字編輯器的搜尋到搜尋引擎的關鍵詞提示都會用到。
本章內容#
- 字串匹配基礎：BF、RK 演算法
- BM 與 KMP：高效的單模式匹配
- Trie 樹：字首樹與自動補全
- AC 自動機：多模式匹配與敏感詞過濾
- 單詞搜尋：Trie + DFS 的綜合應用
演算法分類#
| 類型 | 演算法 | 時間複雜度 | 應用場景 |
|---|---|---|---|
| 單模式匹配 | BF | O(m×n) | 簡單場景 |
| 單模式匹配 | RK | O(n) | 字元集小 |
| 單模式匹配 | BM/KMP | O(n) | 通用高效 |
| 多模式匹配 | Trie | O(n×k) | 字首查詢 |
| 多模式匹配 | AC 自動機 | O(n) | 敏感詞過濾 |
學習順序建議：BF → KMP → Trie → AC 自動機