Xử lý chuỗi

Danh sách đầy đủ các thuật toán trong nhóm (Tổng: 4)

Xử lý chuỗi

Aho-Corasick Algorithm

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

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

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

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.