最长的重复子字符串后缀树dfs

我在执行此操作时遇到了一些麻烦。我知道我需要进行深度优先搜索来找到最深的路径，这将给出子串的索引。有一些问题实施DFS，可能是我缺乏了解：最长的重复子字符串后缀树dfs

int getDeepestPath(TreeNode node) 
{ 
    int maxDistance = 0; 
    TreeNode maxNode; 
    if(node == null) return 0; 
    System.out.println(node.getSuffix()); 
    if(node.getSuffix() != -1) return 0; 
    else 
    { 
     TreeNode nextNode = node.getChild(); 
     while(true) 
     { 
      int distance = 0; 
      if(nextNode != null) 
      { 
       distance = (nextNode.getRightLabel() -nextNode.getLeftLabel()) + 1; 
       System.out.println(distance + " distance"); 
       distance = getDeepestPath(nextNode,t2Info) + distance; 
       if(distance > maxDistance) maxDistance = distance; 
       nextNode = nextNode.getSibling(); 
      } 
      else break; 
     } 
    } 

    System.out.println(maxDistance); 
    return maxDistance; 
}

的最终目的是为了保存最深的节点和长度路径 - 我只是想打印的路径的长度在此刻。

感谢

来源

2013-02-14 drunkmonkey

请问你能解释什么是树节点的“后缀”，“孩子”，“右标签”，“左标签”和“兄弟”？ – 2013-02-14 20:09:10

yes-child是节点的第一个子节点（链表的头部），兄弟节点是共享当前节点父节点的节点，左右标签用于后缀树的短边标签索引 – drunkmonkey 2013-02-14 20:10:25

应该提到后缀== -1意味着该节点是一个分支 – drunkmonkey 2013-02-14 20:21:45

你为什么不只是实现DFS用栈，并添加到node变量称为visited。每次将节点推入堆栈时，标记为visited = true。伪代码

root.visited = true; 
root.push() 
while(Stack.isEmpty()) { 
    if(!root.next.visited) { 
    root.next.push() 
    } 
}

执行查找树叶，进入下一个分支和弹出的逻辑。这是一个通用的逻辑，如果你有一个二叉树，你可以改变这一点，使它更简单，只有两个孩子（左和右）

来源

2013-02-14 20:05:49 noMAD

我不能修改节点代码不幸 – drunkmonkey 2013-02-14 20:22:34

我只是再次阅读你的代码，你只是在寻找最深的（最长的）分支？ I.E树的高度？ – noMAD 2013-02-14 20:30:32

的确如此 – drunkmonkey 2013-02-14 20:32:07

你的假设是错误的。

在后缀树中，每个节点都应该包含在该节点上终止的字符串的键列表。如果列表为空，则该节点不定义任何字符串。没有必要在树中找到长路径。例如，如果树中有三个字符串，“app”（1），“apple”（2）和（5）以及“apple pie”（3），则树会如下所示：

"app" 1 
    | 
"le" 2, 5 
    | 
" pie" 3

来源

2013-02-14 21:56:34

什么假设？ – drunkmonkey 2013-02-14 22:14:35

假设“我需要先进行深度搜索才能找到能够给出子串索引的最深路径” – 2013-02-14 22:18:49

查找最深的分支节点将给出最长重复子串的索引。 – drunkmonkey 2013-02-14 22:24:45

最长的重复子字符串后缀树dfs

回答

相关问题