这是一个(经过轻微测试)版本的代码,可以满足您的要求。您可以轻松地与输入并行遍历结果以定位插入和删除。
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.
(因为“brown”和“yellow”有共同的“ow”等)
修改上面的内容以分割空格(而不是字符数组)并将 String#equals 替换为 == 以获得一个版本,该版本找到单词的最长公共子序列而不是字符,这是相对简单的。对于您上面的示例,该更改将产生明显的结果:
found 7 words
'The'
'quick'
'fox'
'jumped'
'over'
'the'
'dog.'
(您的问题暗示了字符比较,因为您匹配了单词之间的空格。)