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.
Chèn vài từ rồi tra cứu.
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).
Thêm pattern rồi bấm Build.
— 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.
Đảm bảo Module 2 có pattern (bấm Demo nếu cần), rồi Nạp text.