3

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

我的测试输入是：

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更大）。

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

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

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

4 回答 4

2

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

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

current = new ArrayList<SuffixNode>();

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

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

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

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

希望这可以帮助！

于 2013-01-03T20:45:36.903 回答
1

虽然不是答案，但这就是我使用标准集合和 O(n log n) 查找来解决它的方法。

static String findLongestCommonSubstring(String s1, String s2) {
    if (s1.length() > s2.length()) return findLongestCommonSubstring(s2, s1);

    NavigableSet<String> substrings = new TreeSet<>();
    for (int i = 0; i < s1.length(); i++)
        substrings.add(s1.substring(i));
    String longest = "";
    for (int i = 0; i < s2.length(); i++) {
        String sub2 = s2.substring(i);
        String floor = match(substrings.floor(sub2), sub2);
        String ceiling = match(substrings.ceiling(sub2), sub2);
        if (floor.length() > longest.length())
            longest = floor;
        if (ceiling.length() > longest.length())
            longest = ceiling;
    }
    return longest;
}

private static String match(String s1, String s2) {
    if (s1 == null || s2 == null) return "";
    for (int i = 0; i < s1.length() && i < s2.length(); i++)
        if (s1.charAt(i) != s2.charAt(i))
            return s1.substring(0, i);
    return s1.substring(0, Math.min(s1.length(), s2.length()));
}

public static void main(String... args) {
    System.out.println(findLongestCommonSubstring("sdlkjfsdkljfkljsdlfkjaeakjf", "kjashdkasjdlkjasdlfkjaesdlk"));
}

印刷

sdlfkjae
于 2013-01-03T21:59:57.097 回答
0 
public String findCommonSubString(string str1, string str2) {
   string mainStr;
   string otherStr;
   string commonStr = "";
   string foundCommonStr = "";
   boolean strGrowing = false;

   If (str1.length() > str2.length()) {
      mainStr = str1;
      otherStr = str2;
   } else {
      mainStr = str2;
      otherStr = str1;
   }

   int strCount = 0;

   for(int x = 0; x < mainStr.length();x++) {
      strCount = 1;
      strGrowing = true;

      while(strGrowing) {
         if (otherStr.IndexOf(mainStr.substring(x, strCount) >= 0) {
            //Found a match now add a character to it.
            strCount++;

            foundCommonStr = mainStr.substring(x, strCount);

            if (foundCommonStr.length() > commonStr.length()) {
               commonStr = foundCommonStr;
            }
         } else {
            strGrowing = false;
         }
      }

   }

return commonStr;

}
于 2014-03-20T11:43:01.663 回答
0

你必须走后缀树的路线吗？如果没有，你为什么不能：

public String findCommonSubString(string str1, string str2) {
   string mainStr;
   string otherStr;
   string commonStr = "";
   string foundCommonStr = "";
   boolean strGrowing = false;

   If (str1.length() > str2.length()) {
      mainStr = str1;
      otherStr = str2;
   } else {
      mainStr = str2;
      otherStr = str1;
   }

   int strCount = 0;

   for(int x = 0; x < mainStr.length();x++) {
      strCount = 1;
      strGrowing = true;

      while(strGrowing) {
         if (otherStr.IndexOf(mainStr.substring(x, strCount) >= 0) {
            //Found a match now add a character to it.
            strCount++;

            foundCommonStr = mainStr.substring(x, strCount);

            if (foundCommonStr.length() > commonStr.length()) {
               commonStr = foundCommonStr;
            }
         } else {
            strGrowing = false;
         }
      }

   }

return commonStr;

}

我没有运行这个......但我会的。基本上，这将从两个字符串中最小的字符串开始，并尝试使用 IndexOf 和子字符串在两个字符串之间找到一个公共字符串。然后如果确实如此，它将再次检查，但这次通过从较小的字符串中再添加一个字符来检查。如果找到的字符串 (foundCommonStr) 大于 commonStr，它只会将字符串存储在 commonStr 变量中。如果它没有找到匹配项，那么它已经存储了最大的 commonStr 以供返回。

我相信这个想法是合理的，但我没有在编译器中运行它。

于 2013-01-03T21:02:23.147 回答