Wiki › Thuật toán › Thuật toán xâu

Thuật toán xâu

huunguyen Updated Tháng 9. 29, 2026 Đọc 2 phút 4 lượt xem

Trang này là điểm xuất phát cho nhóm thuật toán xâu. Mỗi kỹ thuật có trang riêng với trực giác, ví dụ chạy tay, lỗi thường gặp và bài tập (kể cả đề VOI nếu có).

Lộ trình học gợi ý

Nền tảng so khớp: Hash xâu để so sánh hai xâu con trong $O (1)$ , Hàm tiền tố và KMP và Z-function để tìm pattern, chu kỳ, border trong thời gian tuyến tính.
Tập xâu và từ điển: Trie cho tập từ và XOR lớn nhất, Aho-Corasick khi cần tìm nhiều pattern cùng lúc.
Palindrome: Manacher cho palindrome dài nhất tại mọi tâm, Palindrome Tree cho mọi palindrome con phân biệt.
Cấu trúc hậu tố: Suffix Array (kèm LCP) và Suffix Automaton cho các bài đếm xâu con, xâu con chung dài nhất.

Chọn kỹ thuật nào?

Chỉ cần so sánh hai xâu con nhiều lần, hoặc xâu có cập nhật: hash (ghép với Fenwick hoặc segment tree khi có cập nhật điểm).
Tìm một pattern, chu kỳ ngắn nhất, border: KMP hoặc Z-function; cả hai đều tất định, không lo đụng độ như hash.
Nhiều pattern trên một văn bản: Aho-Corasick.
Câu hỏi về mọi xâu con (đếm xâu con phân biệt, thứ tự từ điển, xâu con chung): suffix array hoặc suffix automaton.

Các trang trong nhóm

Thuật toán	Thời gian	Ứng dụng	Trang
Hash xâu	$O (N)$ dựng, $O (1)$ mỗi truy vấn	So sánh xâu con, LCP bằng chặt nhị phân, hash có cập nhật	Hash xâu
Hàm tiền tố, KMP	$O (N + M)$	Tìm pattern, chu kỳ, automaton KMP	KMP
Z-function	$O (N)$	Tìm pattern, chu kỳ, so tiền tố	Z-function
Trie	$O (‖ s ‖)$ mỗi thao tác	Từ điển, XOR lớn nhất	Trie
Aho-Corasick	$O (\sum ‖ p_{i} ‖ + ‖ t e x t ‖)$	Tìm nhiều pattern đồng thời	Aho-Corasick
Manacher	$O (N)$	Palindrome dài nhất	Manacher
Palindrome Tree	$O (N)$	Mọi palindrome con phân biệt	Palindrome Tree
Suffix Array	$O (N \log N)$	Xâu con, LCP, thứ tự từ điển	Suffix Array
Suffix Automaton	$O (N)$	Đếm xâu con phân biệt, số lần xuất hiện, LCS	Suffix Automaton

Trang này có hữu ích không? Đăng nhập để trả lời

Bình luận

Không có bình luận tại thời điểm này.