Hậu quả từ một túi dây

Question

Cho một chuỗi s, cách hiệu quả nhất để xác định các siêu kết quả ngắn nhất của s từ một chuỗi dây là gì? Ngoài ra, ký tự cuối cùng của s phải khớp với ký tự cuối cùng của siêu dây.

Answer 1

Trừ khi tôi hiểu lầm nó, vấn đề này là chắc chắn nhất trong P.

Một cách tiếp cận ngây thơ sẽ là:

1. Mang tất cả các chuỗi trong B kết thúc với cùng một nhân vật như s. Gọi cái túi mới này B '. Có thể được thực hiện trong O (| B |)
2. Chọn tất cả các chuỗi là các kết quả siêu s trong túi B '. Nó có thể được thực hiện trong O (| B '| * max (| z |)) cho z trong B. Kiểm tra nếu một chuỗi đã cho là một chuỗi của một chuỗi z khác có thể được thực hiện trong O (| z |)
3. Chọn chuỗi ngắn nhất trong số các chuỗi được tìm thấy trước đây (trong O (| B '|))

Where | x | có nghĩa là kích thước của x.

Bạn có thể kết hợp các bước đó, nhưng dù sao thì nó cũng là O (| B | * max (| z |)).

Answer 2

Giả sử túi không thay đổi thường xuyên, tôi sẽ tạo một DAWG và tìm kiếm bằng A *.

Answer 3

Chạy qua từng chuỗi trong túi, kiểm tra xem s có phải là chuỗi con sử dụng tìm kiếm chuỗi nhanh như KMP không. Kiểm tra xem superstrings nào là ngắn nhất. Đây là O(Σlength of strings in bag).

Nếu bạn cần thực hiện tìm kiếm nhiều lần, bạn có thể tạo một dấu đầu dòng cho mỗi chuỗi trong túi và hợp nhất các số này. Sau đó, bạn có thể thực hiện tra cứu trong O(|s|).