字符串与后缀树的隐式表示匹配

 

从Java中的数据结构和算法分析中，Weiss：

“香蕉”的后缀树的显式和隐式表示

韦斯写道：

  • 在叶子中，我们使用后缀开始的索引（如在后缀数组中）
  • 在内部节点中，我们存储从根到内部节点匹配的常用字符的数量; 这个数字代表字母深度。

    • 我的问题：给定输入字符串（例如'香蕉'）和后缀树的隐式表示，子字符串搜索的好算法是什么样子？ 我见过的算法假定树的不同表示。 我想做子串搜索而不转换成不同的树形表示。

    我从来没有见过这种表现。 将边上的标签表示为从原始字符串中勾勒出一系列字符的整数对更为常见，这可以让您更轻松地确定边缘上的字符（您可以回头看看原始字符串字符在需要的基础上，以查看它们是否与您正在查看的子字符串匹配）。

    我相当肯定，这种压缩的表示形式在匹配子字符串方面不太好。 为了追随边缘，你需要知道边缘上的字符是什么，但是除非你扫描原始字符串的字符以找到可能匹配的东西，否则你不能分辨这些字符是什么。 您可以考虑降序到子树中以找到后缀并使用它来重构字符，但这需要额外的时间并打破您期望后缀树的时间范围。

    我最好的猜测是，作者错误地提出了如何在少量空间中表示后缀树。

    链接地址: http://www.djcxy.com/p/40113.html

    上一篇: String matching with an implicit representation of a suffix tree

    下一篇: how to get longest repeating string in substring from suffix tree