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

Question

有一项任务是为后缀列表构建某种字典，例如：

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

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

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

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

Answer 1

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