0

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

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

我需要的答案是：

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

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

谢谢

4

3 回答 3

2

您正在寻找最长的公共子字符串

Java 实现

于 2012-10-19T01:34:47.253 回答
1

搜索最长公共子序列 (LCS)问题和算法。您将从查找两个字符串的 LCS 的算法的实现中获得很多提示。这是一个例子：http: //introcs.cs.princeton.edu/java/96optimization/LCS.java.html

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

于 2012-10-19T01:27:11.047 回答
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;
}
于 2012-11-04T22:36:04.533 回答