java获得两个字符串中相同的最大子字符串

Question

我试图找到两个字符串中最大的子字符串（最小长度为3）。因此，如果我有：

String test1 = "testthatthisworks";
String test2 = "testthisthat";

我需要的答案是：

String[] Answer = ["test", "that", "this"];

我的一个问题是这需要尽可能快。我目前的解决方案是，从最小的字符串开始，使用长度为3的子字符串，然后查看在较大的字符串中是否存在这种情况，如果它确实增加了子字符串的大小，如果不沿1点移动子字符串。问题是，随着字符串长度的增长，这是非常缓慢的。有人能解决这个问题吗

谢谢

Answer 1

这是对LCS algorithm的修改，它将返回所有最大长度匹配 最大尺寸：

public static Collection<String> longestCommonSubstrings(String S1, String S2){
  return longestCommonSubstrings(S1, S2, 0);
}

public static Collection<String> longestCommonSubstrings(String S1, String S2, int minimumLength){

Collection<Integer> indexes = new ArrayList<Integer>();
int Max = minimumLength;

for (int i = 0; i < S1.length(); i++){
  for (int j = 0; j < S2.length(); j++){
    int x = 0;
    int y = Math.min(S1.length()-i,S2.length()-j);
    while (x < y && (S1.charAt(i + x) == S2.charAt(j + x) )){
      x++;
    }
    if (x > Max){
      Max = x;
      indexes = new ArrayList<Integer>();
      indexes.add(i);
    }else if (x == Max){
      indexes.add(i);
    }
  }
}
Collection<String> results = new HashSet<String>();
for (Integer i : indexes){
  results.add(S1.substring(i, (i + Max)));
}
return results;
}

Answer 2

你在找Longest common substring

Java Implementation

Answer 3

搜索最长公共子序列（LCS）问题和算法。通过实现一个查找两个字符串的LCS的算法，您将得到很多提示。下面是一个例子：http://introcs.cs.princeton.edu/java/96optimization/LCS.java.html

如果仔细跟踪LCS算法，它会检索所有公共子字符串，直到找到最长的子字符串。因此，您可以添加一些代码，通过检查这些子字符串的长度来收集它们，即长度>；三,