在一般树遍历中试图找到最大公共子串时陷入寻找最深路径的困境

我正在尝试解决两个字符串之间最大公共子串的问题。我将把我的问题简化为以下内容：我创建了一个通用后缀树 http://en.wikipedia.org/wiki/Generalized_suffix_tree根据我的理解，最大的公共子串是由属于两个字符串的节点组成的最深路径。

我的测试输入是：

String1 = xabc
String2 = abc

看来我构建的树是正确的，但我的问题是以下方法（我最初传递树的根）：

private void getCommonSubstring(SuffixNode node) {  
   if(node == null)  
    return;  
   if(node.from == ComesFrom.Both){  
    current.add(node);          
   }  
   else{  
    if(max == null || current.size() > max.size()){  
        max = current;              
    }  
    current = new ArrayList<SuffixNode>();   
   }  
   for(SuffixNode n:node.children){  
    getCommonSubstring(n);  
   }  
}       

我的目标是，为了找到包含属于两个字符串的节点的最深路径，我将遍历树（预序）并在列表中添加属于两个字符串的节点（current）。一旦我处于不属于两者的节点，我就会更新max列出如果current更大。

但代码是错误的。我对如何实现这一点感到困惑，因为我已经很久没有为通用（非二元）树编写代码了。

你能帮我解决这个问题吗？

Update:
根据@templatetypedef 进行修改。也无法使这项工作成功。

private void getCommonSubstring(SuffixNode node, List<SuffixNode> nodes) {  
   if(node == null)  
    return;  
   if(node.from == ComesFrom.Both){  
    nodes.add(node);              
   }  
   else{  
       if(max == null || current.size() > max.size()){  
       max = nodes;               
    }  
    nodes = new ArrayList<SuffixNode>();  
   }  
   for(SuffixNode n:node.children){  
    List<SuffixNode> tmp = new ArrayList<SuffixNode>(nodes);  
    getCommonSubstring(n, tmp);  
   }  
}  


public class SuffixNode {
    Character character;  
    Collection<SuffixNode> children;  
    ComesFrom from;  
    Character endMarker;  
}  

我在这里看到的一个问题是depth后缀树中的节点与length沿着该路径的绳子。后缀树中的每条边都用一系列字符进行注释，因此由一系列深度为 5 的节点编码的字符串可能比深度为 2 的字符串编码的长度更短。您可能需要调整算法来处理此问题，方法是跟踪迄今为止构建的字符串的有效长度，而不是到目前为止您所追踪的路径中的节点数。

我刚刚注意到的第二个问题是你似乎只有一个current在递归的所有不同分支之间共享的变量。这可能会扰乱你的递归调用状态。例如，假设您位于一个节点，路径长度为 3，并且有两个子节点 - 第一个仅以第一个字符串的后缀结尾，第二个以第一个字符串的后缀结尾两个字符串。在这种情况下，如果您对第一个字符串进行递归调用，您最终将执行该行

current = new ArrayList<SuffixNode>();  

在递归调用中。然后，这将清除您的所有历史记录，因此当您从此调用返回到原始节点并下降到第二个子节点时，您将表现得好像到目前为止还没有建立节点列表，而不是继续从到目前为止您找到的三个节点。

为了解决这个问题，我建议current函数的参数，然后创建一个新的ArrayList当需要时，而不是消灭现有的ArrayList。其他一些逻辑可能也必须改变才能解释这一点。

鉴于此，我建议像这样用伪代码编写该函数（因为我不知道后缀树实现的细节）：

• 如果当前节点为空，则返回0。
• 如果当前节点不是来自两个字符串，则返回 0。
• Otherwise:
  • 设置 maxLen = 0。
  • For each child node:
    • 计算以该节点为根的最长公共子串的长度。
    • 将沿该子项边缘的字符数添加到该长度。
    • 如果 maxLen 超过旧值，则更新 maxLen。
  • 返回最大长度。

希望这可以帮助！