Chúng tôi có hai bộ, A và B. Mỗi bộ trong số này bao gồm các chuỗi. ví dụ: A - {"abwcd", "dwas", "www"} và B - {"opqr", "tops", "ibmd"} Làm cách nào tôi có thể đếm các chuỗi xuất hiện trong tất cả các chuỗi từ tập A , nhưng không có chuỗi nào trong tập B? Ví dụ ở trên câu trả lời là 1 (phần tiếp theo "w").Trie & subsequences
Tất cả điều này một cách tối ưu. Tôi đã nghĩ về việc sử dụng hai lần thử, lần đầu tiên tôi đặt tất cả các chuỗi của tất cả các chuỗi trong B vào trie t_B và sau đó, tôi bắt đầu đặt tất cả các chuỗi của tất cả các chuỗi trong A vào trie t_A, mà không cập nhật trie nếu như vậy sau đó đã được tìm thấy trước đó trong cùng một chuỗi (ví dụ: nếu tôi có chuỗi "aba", tôi không tính số thứ tự "a" hai lần). Theo cách này, nếu tôi tìm thấy một chuỗi có số lần xuất hiện là n (kích thước A) trong t_A, tôi kiểm tra xem nó có nằm trong t_B hay không, và nếu không, tôi sẽ tính. Nhưng điều này là rất rất chậm, nếu A và B có kích thước 15 và các chuỗi dài khoảng 100 ký tự, các chương trình của tôi chạy trong hơn 1 giây.
EDIT: Vì bất kỳ kết thúc con trỏ nào trong ký tự cuối cùng của chuỗi hoặc trong ký tự trước nó, chúng ta không phải phát sinh tất cả các chuỗi, nhưng kết thúc trong ký tự cuối cùng của chuỗi. Khi tôi đẩy chúng vào trie, tôi lưu ý tất cả các nút với 1. Vì vậy, nếu tôi có chuỗi "abcd", tôi chỉ đẩy "abcd", "bcd", "cd" và "d", vì đây nên là ' bộ xương 'của bộ ba. Nhưng đây không phải là một tối ưu hóa rất lớn, tôi vẫn đang tìm kiếm một cái gì đó tốt hơn.
Tôi không ngạc nhiên vì giải pháp của bạn hơi chậm, thuật toán bạn mô tả có thời gian chạy theo thứ tự n^2. Thông thường với những vấn đề như thế này, lập trình động là một cách tiếp cận tốt. Nhưng các vấn đề sau đó nổi tiếng là khó hiểu từ quan điểm thuật toán, vì vậy n^2 có thể là điều tốt nhất bạn có thể hy vọng. – pg1989
Vâng, n^2 là tốt nhất tôi có thể nghĩ ra, sau đó tôi nghĩ về một tối ưu hóa, vì bất kỳ subsqeunce kết thúc trong ký tự cuối cùng của chuỗi hoặc trong một ký tự trước đó, vì vậy bây giờ tôi không tạo ra tất cả các chuỗi , nhưng những cái kết thúc trong ký tự cuối cùng của chuỗi, và whne tôi đẩy chúng vào trie, tôi lưu ý mỗi nút với 1 nút là mới, hoặc tăng nó nếu nó đã ở đó. Vì vậy, nếu tôi có chuỗi "abcd", tôi chỉ đẩy "abcd", "bcd", "cd" và "d", vì đây sẽ là 'bộ xương' của bộ ba. Nhưng đây không phải là một tối ưu hóa rất lớn, tôi vẫn đang tìm kiếm một cái gì đó tốt hơn. –
Tôi nghĩ tốt hơn nên gọi những chất nền đó thay vì các chuỗi. Hậu quả là từ duy nhất chúng tôi có cho một chuỗi có thể được bắt nguồn từ một chuỗi khác bằng cách xóa một số phần tử mà không thay đổi thứ tự của các phần tử còn lại. –