Tạo cây hậu tố của chuỗi S [2..m] từ cây hậu tố của chuỗi S [1..m]

Question

Có cách nhanh (O (1) phức tạp) để tạo ra một suffix tree của chuỗi S [2. .m] từ cây hậu tố của chuỗi S [1..m]?

Tôi quen thuộc với Ukkonen, vì vậy tôi biết cách tạo cây hậu tố nhanh của chuỗi S [1..m + 1] từ cây hậu tố của chuỗi S [1..m], nhưng tôi không thể áp dụng thuật toán cho tình huống ngược lại.

Answer 1

Vâng, như @jogojapan nói, để có được [2..m] cây S từ [1..m] cây S chúng ta cần phải:

• Tìm vị trí-0 lá L.
• Nếu L có nhiều hơn một người anh em, xóa các con trỏ từ L 'mẹ s để L
• Nếu L có chính xác một anh chị em ruột, thay đổi con trỏ từ L' ông bà s để L 's cha mẹ để thay vào đó trỏ đến L của anh chị em của.

@jogojapan hơn nữa cho thấy bạn giữ con trỏ đến lá sâu nhất trong cây. Có hai vấn đề với điều đó: L không nhất thiết phải là lá sâu nhất trên cây, như là Wikipedia's example shows và thứ hai nếu bạn muốn có thể xuất cùng loại cấu trúc dữ liệu như bạn đã nhận được, sau khi xóa L bạn cần phải tìm mới vị trí-0 lá, sẽ mất thời gian O (m).

(Những gì bạn có thể làm là xây dựng một mảng con trỏ cho mỗi lá trong thời gian O (m) và đếm chúng theo vị trí trong một thời gian O (m) khác, sau đó bạn có thể xây dựng tất cả các cây {S [t..n]: 1 < = t < = m} trong thời gian khấu hao liên tục mỗi)

Giả sử bạn không quan tâm trong thời gian khấu hao tuy nhiên, chúng ta hãy chứng minh những gì bạn hỏi là không thể.

• Chúng tôi biết bất kỳ thuật toán nào sửa đổi cây hậu tố của S [1..m] phải bắt đầu từ gốc: nó không thể bắt đầu ở bất kỳ nơi nào khác vì chúng tôi không biết gì về cấu trúc dữ liệu cụ thể bên dưới. Không biết rằng các nút của cây có con trỏ con trỏ, do đó, vị trí duy nhất mà toàn bộ cây có thể truy cập được từ gốc.
• Chúng tôi cũng biết rằng nó phải xác định vị trí lá vị trí 0 trước khi nó có thể hy vọng sửa đổi cấu trúc dữ liệu thành cây hậu tố cho S [2..m]. Để làm điều này, nó rõ ràng phải đi qua tất cả các nút giữa gốc và lá vị trí-0.
• Thing là, xem xét các cây hậu tố của a^m (nhân vật một lặp đi lặp lại m lần): chiều dài của con đường là m-1. Vì vậy, bất kỳ thuật toán nào cũng phải truy cập ít nhất m-1 nút và do đó mất thời gian O (m) trong trường hợp xấu nhất.