c - 后缀列表中的内存有效搜索

Question

有一个任务是为后缀列表，例如:

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

对于每个传入的字符串，例如“test.some.org”。在内置字典中找到最长的后缀。有一些内存限制。这种情况下最合适的算法/数据结构是什么？

对我来说最明显的选择是反向字符串的 trie，但它似乎非常耗费内存。我试过使用后缀数组，但它看起来不适合这项任务。

字典是不可变的，必须构建一次。不可变尝试的内存效率更高的表示形式吗？

Answer 1

对于一组不可变的字符串，compressed trie效果很好。主要思想是将 trie 中的单个分支表示为一个节点。网络上有很多关于此方法的有用描述/论文。