これは、あなたが求めたことを実行する(軽くテストされた)バージョンのコードです。入力と並行して結果を簡単にトラバースして、挿入と削除を見つけることができます。
public class StringDiff {
private static int length(String s) { return s == null ? 0 : s.length(); }
private static char[] chars(String s) { return s == null ? new char[0] : s.toCharArray(); }
private final String left;
private final String right;
private final char[] lccs;
private final String lcs;
public StringDiff(String left, String right) {
this.left = left;
this.right = right;
lccs = init();
lcs = new String(lccs);
}
public String getLcs() { return lcs; }
public char[] getLccs() { return lccs.clone(); }
private char[] init() {
int lLength = length(left);
int rLength = length(right);
char[] lChars = chars(left);
char[] rChars = chars(right);
int [][] t = new int [lLength + 1][rLength + 1];
for (int i = lLength - 1; i >= 0; --i) {
for (int j = rLength - 1; j >= 0; --j) {
if (lChars[i] == rChars[j]) {
t[i][j] = t[i + 1][j + 1] + 1;
} else {
t[i][j] = Math.max(t[i + 1][j], t[i][j + 1]);
}
}
}
char[] result = new char[t[0][0]];
int l = 0, r = 0, p = 0;
while (l < lLength && r < rLength) {
if (lChars[l] == rChars[r]) {
result[p++] = lChars[l++];
r++;
} else {
if (t[l + 1][r] > t[l][r + 1]) {
++l;
} else {
++r;
}
}
}
return result;
}
}
それによると、元の入力の実際の最長のサブシーケンス:
The quick brown fox jumped over the lazy dog.
The quick yellow fox jumped over the well-bred dog.
は:
The quick ow fox jumped over the l dog.
(「茶色」と「黄色」は「わ」が共通しているためなど)
上記を (char 配列ではなく) 空白で分割するように変更し、== を String#equals に置き換えて、文字の代わりに単語の最長の共通サブシーケンスを見つけるバージョンを取得するのは比較的簡単です。上記の例では、その変更により明らかな結果が得られます。
found 7 words
'The'
'quick'
'fox'
'jumped'
'over'
'the'
'dog.'
(単語間のスペースを一致させたため、質問は文字の比較を暗示していました。)