Xử lý chuỗi nâng cao

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

Xử lý chuỗi nâng cao

Suffix Automaton (Blumer Algorithm)

Thời gian (Time) O(N)
Không gian (Space) O(N)

Mô tả nguyên lý

Cấu trúc tự động hữu hạn nhận diện toàn bộ hậu tố của chuỗi với kích thước tối ưu tuyến tính.

Cài đặt mẫu (Implementation)

// Mở rộng trạng thái tự động qua từng ký tự mới thêm vào chuỗi.
Xử lý chuỗi nâng cao

Ukkonen Algorithm (Suffix Tree)

Thời gian (Time) O(N)
Không gian (Space) O(N)

Mô tả nguyên lý

Thuật toán xây dựng cây hậu tố (Suffix Tree) trực tuyến trong thời gian tuyến tính.

Cài đặt mẫu (Implementation)

// Sử dụng các con trỏ mở rộng, điểm dừng (suffix links) để cập nhật cây hiệu quả theo thời gian thực.