Làm cách nào để tìm chuỗi con dài nhất bằng cây?

Question

Vấn đề chuỗi con thường gặp nhất theo wiki có thể được giải quyết bằng cách sử dụng cây hậu tố.
Từ wiki:

Các chuỗi con chung dài nhất của một tập hợp các chuỗi có thể được tìm thấy bằng cách xây dựng một cây hậu tố tổng quát cho các dây, và sau đó tìm các nút nội bộ sâu sắc mà có nút lá từ tất cả các chuỗi trong cây con bên dưới nó

Tôi không hiểu.
Ví dụ: nếu tôi có:
ABCDE và XABCZ
sau đó cây hậu tố là (một số chi nhánh từ XABCZ bỏ qua do không gian):

Các chuỗi con chung dài nhất là ABC nhưng nó không phải là tôi có thể không thấy cách mô tả wiki trợ giúp ở đây.
ABC không phải là các nút bên trong sâu nhất với các nút lá.
Bất kỳ trợ giúp nào để hiểu cách hoạt động của tính năng này?

Answer 1

Bạn chưa thực sự vẽ cây hậu tố. Bạn đã thực hiện nó đúng cách, ở gốc bạn sẽ chỉ có mọi nhân vật có thể một lần. Cây chỉ tách khi một chữ cái có thể có nhiều hậu tố sau. Điều đó buộc các chất nền chung vào nhau làm cho chúng có thể tìm thấy được.

Answer 2

Giống như những gì đã nói trước đây, cây của bạn không chính xác.

Đây là những gì tôi nhận được khi chạy "ABCDE $ XABCZ" thông qua mã của tôi.

Suffix Tree code:

String = ABCDE$XABCZ$ 
End of word character 1 = $ 
└── (0) 
    ├── (20) $ 
    ├── (22) ABC 
    │ ├── (15) DE$ 
    │ └── (23) Z$ 
    ├── (24) BC 
    │ ├── (16) DE$ 
    │ └── (25) Z$ 
    ├── (26) C 
    │ ├── (17) DE$ 
    │ └── (27) Z$ 
    ├── (18) DE$ 
    ├── (19) E$ 
    ├── (21) XABCZ$ 
    └── (28) Z$ 

Trong một (compact) cây hậu tố, bạn cần phải tìm nút nội bộ sâu nhất (s) có các nút lá từ tất cả các chuỗi. Nếu bạn có nhiều nút ở cùng độ sâu, bạn phải so sánh độ dài của chuỗi được biểu thị bằng nút đó. tức là ABC, BC và C đều có độ sâu tương tự, vì vậy bạn phải so sánh độ dài của các chuỗi ABC, BC và C để xem cái nào dài hơn; đó là ABC rõ ràng.

Suffix Trie code:

└── null 
    ├── A 
    │ └── B 
    │  └── C 
    │   ├── D 
    │   │ └── (E) ABCDE 
    │   └── (Z) ABCZ 
    ├── B 
    │ └── C 
    │  ├── D 
    │  │ └── (E) BCDE 
    │  └── (Z) BCZ 
    ├── C 
    │ ├── D 
    │ │ └── (E) CDE 
    │ └── (Z) CZ 
    ├── D 
    │ └── (E) DE 
    ├── (E) E 
    ├── X 
    │ └── A 
    │  └── B 
    │   └── C 
    │    └── (Z) XABCZ 
    └── (Z) Z 

Trong một (không compact) cây hậu tố, tìm nút nội bộ sâu nhất (s) có các nút lá từ tất cả các chuỗi.

Hy vọng điều đó sẽ hữu ích.