java - 坚持在一般树遍历中寻找最深路径试图找到最大的公共(public)子串

Question

我正在尝试解决 2 个字符串之间的最大公共(public)子串问题。我将把我的问题简化为以下内容:我创建了一个 general suffix tree根据我的理解，最大的公共(public)子串是由属于两个字符串的节点组成的最深路径。

我的测试输入是:

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 列表。

但是代码是错误的。而且我对如何实现这一点感到困惑，因为我已经很久没有为一般(非二叉)树编写代码了。

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

更新:
根据@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;  
}  

Answer 1

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

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

current = new ArrayList<SuffixNode>();  

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

要解决这个问题，我建议将 current 作为函数的参数，然后在需要时创建一个新的 ArrayList，而不是清除现有的 数组列表。其他一些逻辑可能也必须更改才能解决这个问题。

鉴于此，我建议用这样的伪代码编写函数(因为我不知道您的后缀树实现的细节):

• 如果当前节点为null，则返回0。
• 如果当前节点不是来自两个字符串，则返回0。
• 否则:
  • 设置 maxLen = 0。
  • 对于每个子节点:
    • 计算以该节点为根的最长公共(public)子串的长度。
    • 在该长度上加上该 child 边缘的字符数。
    • 如果这超过旧值，则更新 maxLen。
  • 返回 maxLen。

希望这对您有所帮助!