內存有效的搜索

Question

有一個任務建立某種字典爲後綴的 列表，一個實例：

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

，併爲每個到來的字符串，一個實例「test.some org「的。找到建立的詞典中最長的後綴。有一些內存限制。這種情況最適合的算法/數據結構是什麼？

對我來說，最明顯的選擇是反轉字符串，但它似乎非常消耗內存。我試圖使用後綴數組，但它看起來不適合任務。

字典是不可變的，它必須被構建一次。是不變的嘗試更有效的內存表示？

Answer 1

對於不可變的一組字符串，compressed trie工作得很好。主要想法是將trie中的單個分支表示爲一個節點。網絡中有這種方法的許多有用的描述/論文。