tìm kiếm hiệu quả trong danh sách suffix

Question

Có một nhiệm vụ để xây dựng một số loại của một từ điển cho danh sách các hậu tố, cho một ví dụ:

[., .com., a.com., a.b.com., org., some.org., ...] 

và cho mỗi chuỗi đến, cho một ví dụ "test.some .org. " tìm hậu tố dài nhất trong từ điển được xây dựng. Có một số hạn chế về bộ nhớ. Cấu trúc dữ liệu/cấu trúc dữ liệu thích hợp nhất cho trường hợp này là gì?

Sự lựa chọn rõ ràng nhất đối với tôi là bộ ba cho chuỗi bị đảo ngược, nhưng dường như rất tốn bộ nhớ. Tôi đã cố gắng sử dụng mảng hậu tố nhưng có vẻ như nó không phù hợp với nhiệm vụ.

Từ điển không thay đổi được, nó phải được tạo một lần. Các đại diện có hiệu quả về bộ nhớ của những cố gắng bất biến hơn?

Answer 1

Đối với một chuỗi không thay đổi, compressed trie hoạt động rất tốt. Ý tưởng chính là đại diện cho một nhánh đơn trong trie như một nút. Có nhiều mô tả/giấy tờ hữu ích của phương pháp này trên web.