Pattern matching & String

Module 2 — Pattern matching & String: tổng quan

Lộ trình module string matching: từ naive O(n·m) tới KMP, Rabin-Karp, Z-function và Aho-Corasick đa mẫu. Học gì, vì sao, làm được gì.

Naive string matching — vì sao O(n·m) chậm

Thuật toán so khớp chuỗi ngây thơ: trượt pattern qua text, so từng vị trí. Vì sao worst-case O(n·m) và khi nào vẫn đủ dùng trong thực tế.

KMP — failure function & matching O(n+m)

Knuth-Morris-Pratt dùng failure function (prefix function) để không bao giờ quay lui con trỏ text, đạt O(n+m). Cách xây bảng failure, vì sao nó đúng, và trace từng bước.

Rabin-Karp — rolling hash cho đa mẫu

So khớp bằng hash: tính hash cửa sổ trượt trong O(1) nhờ rolling hash. Mạnh khi tìm nhiều pattern cùng lúc; rủi ro hash collision.

Z-function — z-array và ứng dụng

Z-array[i] = độ dài tiền tố chung dài nhất của chuỗi với hậu tố bắt đầu tại i. Tính O(n) bằng z-box; ứng dụng matching và đếm lặp.

Aho-Corasick — automaton so khớp đa mẫu

Trie nhiều pattern + failure link tạo automaton tìm tất cả pattern trong một lần quét O(n+z). Nền của antivirus và IDS signature scanning.

Mini-challenge — tự viết grep bằng KMP

Lab: cài công cụ tìm tất cả vị trí xuất hiện của pattern trong file bằng KMP, đo so với naive trên input adversarial.

Case study — Lucene index & ClamAV signature

Hai hệ thống thật: Lucene dùng cấu trúc gì để search nhanh, và ClamAV quét triệu signature virus bằng Aho-Corasick ra sao.

Module 2 — Tổng kết & cheat sheet

Recap string matching: bảng so sánh naive/KMP/Rabin-Karp/Z/Aho-Corasick theo single vs multi-pattern, preprocessing, glossary, self-assessment.