Xử lý chuỗi
Aho-Corasick Algorithm
ID: #82
Xem trên trang chủ
Thời gian (Time)
O(n + m + z)
Không gian (Space)
O(m * sigma)
Mô tả nguyên lý
Tìm kiếm nhiều từ khóa đồng thời trong văn bản.
Cài đặt mẫu (Implementation)
// Xây dựng Cây tiền tố kết hợp con trỏ thất bại tương tự KMP mở rộng.
Xử lý chuỗi
Aho-Corasick Multi-Pattern Matching
ID: #448
Xem trên trang chủ
Thời gian (Time)
O(N + M + Z)
Không gian (Space)
O(Alphabet * States)
Mô tả nguyên lý
Tìm kiếm đồng thời nhiều mẫu từ khóa trong văn bản sử dụng cây Trie kết hợp con trỏ thất bại (failure links).
Cài đặt mẫu (Implementation)
// Xây dựng cây từ điển tiền tố và liên kết bước nhảy chuyển đổi trạng thái tối ưu.
Xử lý chuỗi
Manacher Algorithm
ID: #83
Xem trên trang chủ
Thời gian (Time)
O(n)
Không gian (Space)
O(n)
Mô tả nguyên lý
Tìm chuỗi con đối xứng (Palindrome) dài nhất với thời gian tuyến tính.
Cài đặt mẫu (Implementation)
// Tận dụng tính đối xứng đã duyệt qua để tránh tính toán trùng lặp.
Xử lý chuỗi
Suffix Automaton
ID: #84
Xem trên trang chủ
Thời gian (Time)
O(n)
Không gian (Space)
O(n * sigma)
Mô tả nguyên lý
Đồ thị định hướng biểu diễn tất cả các hậu tố của một chuỗi.
Cài đặt mẫu (Implementation)
// Cấu trúc tự động trạng thái tối ưu nén toàn bộ tập hợp chuỗi con.