用于为部分%infix%搜索索引数据的数据结构是什么？

Question

想象一下,您有大量的数据缓存,可以通过4种方式进行搜索:

1. 完全符合
2. 字首%
3. %后缀
4. %缀%

我正在使用Trie进行前3种类型的搜索,但除了顺序处理大量元素之外,我无法弄清楚如何处理第四种类型.

Answer 1

您可以为 2（键按正常顺序）和 3（键顺序相反）构建可导航的映射或集（例如 TreeMap 或 TreeSet）

对于选项 4，您可以构建一个集合，其中每个起始字母都有一个键。您可以根据您的要求简化此操作。这可能会导致使用更多空间，但查找时间为 O(log n)。