Hiểu thuật toán của Ukkonen cho hậu tố cây

Question

Tôi đang làm một số công việc với thuật toán của Ukkonen để xây dựng cây hậu tố, nhưng tôi không hiểu một số phần của lời giải thích của tác giả vì nó phức tạp về thời gian tuyến tính.

Tôi đã học được thuật toán và đã mã hóa nó, nhưng giấy mà tôi đang sử dụng làm nguồn thông tin chính (được liên kết dưới đây) rất khó hiểu ở một số phần nên không rõ ràng tại sao thuật toán là tuyến tính .

Bất kỳ trợ giúp nào? Cảm ơn.

Liên kết với giấy Ukkonen của: http://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf

Answer 1

Tìm một bản sao của Gusfield của string algorithms textbook. Nó có giải thích tốt nhất về việc xây dựng cây hậu tố mà tôi đã thấy. Độ tuyến tính là kết quả đáng ngạc nhiên của một số tối ưu hóa của thuật toán cấp cao.