Lesson 43 — Trie & Aho-Corasick
Ba module: (1) xây Trie & tra prefix, (2) xây Aho-Corasick automaton với failure links, (3) chạy text qua automaton để bắt nhiều pattern cùng lúc. Đọc lý thuyết ở nút 📖 Đọc README.
1. Trie builder — cây prefix
Chèn từ vào trie, vẽ cây (node tô đậm = kết thúc từ). Rồi search (cả từ) hoặc prefix (tiền tố) — đường đi sẽ được highlight.
2. Aho-Corasick automaton — Trie + failure links
Build trie của các pattern rồi BFS theo level xây failure link (mũi tên đứt đỏ). Mỗi node hiện output (pattern kết thúc, đã gộp failure chain).
— Cạnh đen liền = trie (goto) · — — → đỏ đứt = failure link · node viền xanh đậm = có output.
3. AC matching — chạy text, bắt nhiều pattern
Dùng các pattern ở Module 2. Con trỏ chạy qua text: có child thì đi xuống, không thì tụt failure; báo mọi output. Mỗi pattern một màu.
Thử: nhập nhiều pattern rồi chạy text MỘT lượt — failure link cho phép "rơi" sang pattern khác giữa chừng, không sót match nào.