找到包含在字典中的最长前缀

我正在实施Lempel-Ziv压缩，并提出了一个问题。找到包含在字典中的最长前缀

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

即给出的字符串：

0 : AABB 
1 : ABA 
2 : AAAB

和查询字符串“AABBABA”我希望能够做到这一点返回查找“0”这应该在时间线需做的长度前缀。

我希望能够在字典中不断添加新的前缀'AABBAB'。

有没有一个标准的，简单的方法/算法来做到这一点？

我最初的想法是建立一个带有指针列表的标准n路树并且只是搜索这个？

“线性时间”是否意味着您希望字典查找的复杂度与字母大小S无关？根据它的声音，“标准n路”树可能具有多达S个传出边缘的每个节点。 – jogojapan 2012-04-14 12:06:13

@jogojapan：你是对的，我的意思是线性关于长度。并为常数，如果在字母表中的平均线性;-) – 2012-04-14 12:34:17

您正在描述一个简单的trie查找，不同之处在于，即使存在多余字符，也要返回叶节点。

不知道你在用n-way树思考什么，但很可能它完全一样，因为它是明显的解决方案：v）。如果你想更有效率，你可以看看不同种类的尝试。

2012-04-14 11:54:37 Potatoswatter

如何添加“新前缀'AABBAB'”在一个简单的搜索trie中定时工作？ – jogojapan 2012-04-14 11:55:47

@jogojapan：通过持有返回的节点，并添加尾巴:-) – 2012-04-14 11:56:07

好的。无可否认，我将“简单的特里”解释为在过渡时具有个人特征的人。也许是我的错误。 – jogojapan 2012-04-14 11:58:18

回答