我正在尝试使用ukkonen的后缀树来比较文档 .
在这一点上，我关注两件事：
-
首先，我正在尝试为一个文档生成后缀树，然后使用该后缀树查找该文档中的所有常见子串 .
-
接下来是识别两个文档之间的所有常见子字符串 .
我能够基于http://marknelson.us/1996/08/01/suffix-trees/为文档生成ukkonen后缀树 . 并搜索给定的子字符串 . 但我仍然无法找到识别给定文档中所有常见子串的方法 . 你能告诉我一种方法吗 . 我正在使用visual c .
我们可以使用ukkonen的算法来比较两个文档并识别它们之间的所有常见子串吗？如果是这样，请逐步解释 .
Ukkonen's suffix tree algorithm in plain English?对Ukkonen的后缀树有一个很好的解释
1 回答
如果您有两个文档，则可以使用Ukkonen算法为两个文档构建generalized suffix tree，然后执行后处理步骤以清除不可能的配置 .
获得通用后缀树后，可以在树上运行DFS，以标识树中具有与每个文档的后缀对应的叶的每个内部节点 . 这些节点中的每一个对应于两个文档共有的子字符串，因为每个节点对应于两个字符串的后缀的前缀 .
从那里，你可以做那些最合理的子串 . 如果您想要最长的公共子字符串，只需搜索在第一步中标记的字符串深度最高的节点 . 如果要查找所有这些子字符串，可以迭代所有这些节点并打印出沿途累积的每个子字符串 .