Giao diện
Xử lý chuỗi — String Processing
Khi hệ thống Intrusion Detection của Cloudflare quét hàng triệu packet mỗi giây để phát hiện malware signature, hay khi Google autocomplete trả kết quả gợi ý trong dưới 50ms cho 8.5 tỷ truy vấn mỗi ngày — phía sau đều là các thuật toán xử lý chuỗi đang hoạt động ở production scale.
Brute-force pattern matching với O(n × m) hoàn toàn không chấp nhận được khi text là file log 10GB hay genome 3 tỷ nucleotide. Section này trang bị cho bạn bốn thuật toán cốt lõi — mỗi thuật toán tối ưu cho một lớp bài toán riêng, từ single-pattern search đến multi-pattern matching trên hàng nghìn keyword đồng thời.
Lộ trình học
Bốn thuật toán trong section được sắp xếp theo dependency logic — mỗi bài xây trên kiến thức của bài trước:
text
┌─────────────────────────────────────────────────────────┐
│ LỘ TRÌNH HỌC │
│ │
│ ┌───────┐ ┌─────────────┐ │
│ │ KMP │───────► │ Aho-Corasick│ (KMP trên Trie) │
│ └───────┘ └─────────────┘ │
│ │ ▲ │
│ │ ┌──────┘ │
│ ▼ │ │
│ ┌───────────┐ ┌───────┐ │
│ │ Rabin-Karp│ │ Trie │ │
│ └───────────┘ └───────┘ │
│ │
│ Foundation ──────────────────────────► Advanced │
└─────────────────────────────────────────────────────────┘Thứ tự đề xuất:
- KMP — Nắm vững nguyên lý failure function trước, đây là nền tảng tư duy cho cả section
- Rabin-Karp — Tiếp cận bài toán từ góc nhìn hoàn toàn khác: hash thay vì so sánh ký tự
- Trie — Cấu trúc dữ liệu cây tiền tố, nền tảng cho Aho-Corasick
- Aho-Corasick — Đỉnh cao: kết hợp Trie + failure links cho multi-pattern matching
Nội dung
Thuật toán tìm kiếm đơn mẫu (Single-Pattern)
| Bài học | Mức độ | Thời gian | Ý tưởng chính |
|---|---|---|---|
| KMP — Knuth-Morris-Pratt | Intermediate | 30 phút | Failure function, prefix table, O(n + m) deterministic |
| Rabin-Karp — Rolling Hash | Intermediate | 25 phút | Polynomial hashing, O(1) window slide, multi-pattern cùng độ dài |
Cấu trúc dữ liệu & Thuật toán đa mẫu (Multi-Pattern)
| Bài học | Mức độ | Thời gian | Ý tưởng chính |
|---|---|---|---|
| Trie — Cây tiền tố | Intermediate | 25 phút | Prefix tree, autocomplete, compressed trie, IP routing |
| Aho-Corasick — Multi-Pattern Matching | Advanced | 35 phút | Automaton construction, failure links, output links, O(n + m + z) |
Bảng so sánh nhanh
| Tiêu chí | KMP | Rabin-Karp | Trie | Aho-Corasick |
|---|---|---|---|---|
| Bài toán | 1 pattern | 1+ pattern (cùng dài) | Prefix queries | k patterns bất kỳ |
| Thời gian | O(n + m) | O(n + m) expected | O(L) per query | O(n + m + z) |
| Worst case | O(n + m) ✅ | O(n × m) ❌ | O(L) ✅ | O(n + m + z) ✅ |
| Streaming | ✅ | ✅ | ❌ | ✅ |
| Ứng dụng chính | Text editor, DNA | Plagiarism, rsync | Autocomplete, DNS | IDS, antivirus |
Khi nào dùng thuật toán nào?
- 1 pattern, cần đảm bảo worst case → KMP
- Nhiều patterns cùng độ dài, hoặc cần fingerprint → Rabin-Karp
- Prefix search, autocomplete, dictionary → Trie
- 10+ patterns tùy ý, quét real-time → Aho-Corasick
🧠 Quiz
Câu 1: Rabin-Karp khác KMP ở điểm nào trong cách tiếp cận?
- [ ] A) Rabin-Karp nhanh hơn KMP trong mọi trường hợp
- [x] B) Rabin-Karp dùng hash function để so sánh nhanh, KMP dùng prefix table để tránh quay lại
- [ ] C) KMP không dùng được cho chuỗi Unicode
- [ ] D) Rabin-Karp chỉ tìm được 1 occurrence
💡 Giải thích: KMP: xây failure function → sliding comparison không lùi lại text → O(n+m) deterministic. Rabin-Karp: rolling hash → so sánh hash O(1) → average O(n+m), worst O(nm) khi nhiều hash collision. Rabin-Karp mạnh hơn khi tìm nhiều pattern cùng lúc.
Câu 2: Trie có độ phức tạp tìm kiếm một từ dài m là bao nhiêu?
- [ ] A) O(n) với n = tổng số từ trong Trie
- [x] B) O(m) — chỉ phụ thuộc độ dài từ cần tìm, không phụ thuộc số từ trong Trie
- [ ] C) O(m × n)
- [ ] D) O(log n)
💡 Giải thích: Trie duyệt theo từng ký tự: mỗi ký tự → đi xuống 1 level. Tìm từ dài m = đi qua m cạnh = O(m). Không phụ thuộc vào Trie chứa 100 hay 1 triệu từ! Đây là ưu điểm lớn so với hash map khi cần prefix operations.