c++ - 查找字典中包含的最长前缀

Question

我正在实施 Lempel-Ziv 压缩，我想到了一个问题。

给定一个“字典”和一个字符串。我希望能够计算字典中包含的字符串的最长前缀。

这是给定的字符串：

0 : AABB
1 : ABA
2 : AAAB

和查询字符串 'AABBABA' 我希望能够进行返回 '0' 的查找，这应该在与前缀长度成线性关系的时间内完成。

接下来我希望能够在恒定时间内将新前缀“AABBAB”添加到字典中。

是否有标准且简单的方法/算法来执行此操作？

我最初的想法是用指针列表构建一个标准的 n 路树，然后搜索它？

Answer 1

您正在描述一个简单的trie查找，但即使有多余的字符，您也会返回一个叶节点。

不确定您对 n 路树的想法，但很可能是完全相同的，因为它是显而易见的解决方案 :v) 。如果你想更有效率，你可以研究不同类型的尝试。