如何从字符串集合中匹配最特定前缀，可使用后缀树等数据结构实现吗

你的需求本质是前缀匹配查询：找出所有预存字符串是输入查询串前缀的条目，按预存字符串长度降序排列就是你要的「最特定到最不特定」的顺序，升序排列即可实现反向遍历。

可选数据结构 #

完全可以用现有数据结构实现，优先推荐前缀树（Trie），不推荐使用后缀树：

• 前缀树是专门为前缀匹配场景设计的结构，实现简单，查询效率和查询串长度正相关，完全适配你的需求
• 后缀树是针对后缀查询场景设计的，用于该前缀场景会产生大量不必要的空间和性能浪费，投入产出比极低

具体实现逻辑 #

1. 构建前缀树时，每个对应预存字符串末尾的节点，存储该字符串关联的业务数据
2. 处理查询请求时，从根节点出发，按查询串字符从左到右遍历前缀树路径，每走到一个存储了业务数据的节点，就将对应的（字符串, 数据）元组加入结果集
3. 遍历到查询串末尾，或者树路径中断时停止查询
4. 最终将结果集按预存字符串的长度倒序排列，即可得到从最特定到最不特定的排序结果，正序排列即可实现反向遍历

示例验证 #

以你给出的预存集合为例：

"abc" -> data_1
"xyz" -> data_2
"abcpqr" -> data_3
"abcpqrstu" -> data_4
"xyzpqr" -> data_2

• 查询abcpqr时，遍历过程中会命中abc、abcpqr两个带数据的节点，按长度倒序后输出结果和你给出的示例完全一致
• 查询abcpqrstu时，会命中abc、abcpqr、abcpqrstu三个节点，倒序后输出符合预期
• 查询abcpq时，仅命中abc节点，输出和示例一致

内容的提问来源于stack exchange，提问作者peter