0

両方の文字列に含まれる最大の部分文字列を見つけようとしています (最小長は 3)。だから私が持っている場合：

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

私は答えが必要です：

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

私の1つの問題は、これをできるだけ速くする必要があることです。私の現在の解決策は、最小の文字列から長さ 3 の部分文字列を使用して、これがより大きな文字列に存在するかどうかを確認することです。問題は、文字列が長くなるにつれてこれが非常に遅くなることです。誰でもこの問題の解決策を持っていますか?

ありがとう

4

3 に答える 3

2

最長の共通部分文字列を探しています

Java 実装

于 2012-10-19T01:34:47.253 に答える
1

Longest Common Subsequence (LCS)の問題とアルゴリズムを検索します。2 つの文字列の 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 に答える