Java：如何比较两个字符串以获得它们不同的部分？

Question

我希望学习一种方法来获取两个字符串不同的部分。

假设我有这两个字符串：

String s1 = "x4.printString(\"Bianca.()\").y1();";
String s2 = "sb.printString(\"Bianca.()\").length();";

我希望从一个方法接收s1和s2作为参数，并输出如下内容：["x4", "y1", "sb", "length"]。我在其他帖子中寻找过类似的方法，但只找到了指向StringUtils.difference(String first, String second)的链接。但是这个方法返回第二个字符串与第一个字符串开始不同的位置。
我真的不知道从哪里开始，任何建议都将不胜感激。
更新： 根据@aUserHimself的建议，我设法获得两个字符串的所有公共子序列，但这些子序列像一个唯一的字符串一样出现。
这是我的代码：

private static int[][] lcs(String s, String t) {
    int m, n;
    m = s.length();
    n = t.length();
    int[][] table = new int[m+1][n+1];
    for (int i=0; i < m+1; i++)
        for (int j=0; j<n+1; j++)
            table[i][j] = 0;
    for (int i = 1; i < m+1; i++)
        for (int j = 1; j < n+1; j++)
            if (s.charAt(i-1) == t.charAt(j-1))
                table[i][j] = table[i-1][j-1] + 1;
            else
                table[i][j] = Math.max(table[i][j-1], table[i-1][j]);
    return table;
}

private static List<String> backTrackAll(int[][]table, String s, String t, int m, int n){
    List<String> result = new ArrayList<>();
    if (m == 0 || n == 0) {
        result.add("");
        return result;
    }
    else
        if (s.charAt(m-1) == t.charAt(n-1)) {
            for (String sub : backTrackAll(table, s, t, m - 1, n - 1))
                result.add(sub + s.charAt(m - 1));
            return result;
        }
        else {
            if (table[m][n - 1] >= table[m - 1][n])
                result.addAll(backTrackAll(table, s, t, m, n - 1));
            else
                result.addAll(backTrackAll(table, s, t, m - 1, n));
            return result;
        }
}

private List<String> getAllSubsequences(String s, String t){
    return backTrackAll(lcs(s, t), s, t, s.length(), t.length());
}

调用getAllSubsequences函数来处理这两个字符串：

String s1 = "while (x1 < 5)"
String s2 = "while (j < 5)"

我收到的字符串是["while ( < 5)"]，而不是["while (", " < 5)"]，我希望得到后者。我不明白我的错误在哪里。

- delca85

---

@downvoter：为什么要踩？因为格式不够优秀吗？ - delca85

不太理解为什么会有关闭投票，这个问题很清晰明了。 - Tobb

我不明白这个问题。x4是什么，sb是什么？y1又是什么？我不知道你想要比较的字符串值是什么。所以@Tobb请给我解释一下。 - GhostCat

@GhostCat 它们是正在进行比较的两个字符串的一部分。 - Tobb

@GhostCat x4 是第一个不同的字符串部分，然后 .printString("Bianca.()"). 是相同的，因此将被跳过，接着 y1 再次不同，而 (); 再次相同并被跳过 - 对于第一个 String。然后对于第二个 String，sb 不同，而 length 则不同。 - aUserHimself

Answer 1

在两个字符串之间找到最长的公共子序列。然后可以使用indexOf获取此公共字符串在两个字符串之间的索引，并从两个字符串中提取不同的值。

例如:

CICROSOFK
WOCROSFGT

常见的信件为：

CROS

从0到SOFT的索引位置和从index+'SOFT'.length到str.length的位置找出不同的字符串。

- rohitanand

---

也许你是对的：我可以找到最长公共子序列，然后从两个字符串中删除它。通过迭代这个过程，我可以获取两个字符串不同的部分。 - delca85

Answer 2

我已经标记了一个重复的问题（链接），其答案使用最长公共子序列来比较两个字符串。

因此，您可以递归地应用它，并在每次新递归时使用占位符来标记找到此LCS的部分，以便您可以标记不同的部分。最后，当不存在更多的公共序列时，您将不得不通过占位符拆分每个字符串并获取所需的部分。

更新1: 如果我现在重新考虑，这个递归部分可能不会导致最优解（从总执行时间的角度来看），因为您将多次迭代字符串。但是，可以通过重用（缩小版本的）记忆化表从一次迭代中检索所有序列，查看this implementation和this more detailed one。

更新2: 我已经成功实现了基于this code的递归版本（不是最优解）：

public class LongestCommonSequence {

    private final char[] firstStr;
    private final char[] secondStr;
    private int[][] LCS;
    private String[][] solution;
    private int max = -1, maxI = -1, maxJ = -1;
    private static final Character SEPARATOR = '|';

    public LongestCommonSequence(char[] firstStr, char[] secondStr) {
        this.firstStr = firstStr;
        this.secondStr = secondStr;
        LCS = new int[firstStr.length + 1][secondStr.length + 1];
        solution = new String[firstStr.length + 1][secondStr.length + 1];
    }

    public String find() {

        for (int i = 0; i <= secondStr.length; i++) {
            LCS[0][i] = 0;
            if(i > 0) {
                solution[0][i] = "   " + secondStr[i - 1];
            }
        }

        for (int i = 0; i <= firstStr.length; i++) {
            LCS[i][0] = 0;
            if(i > 0) {
                solution[i][0] = "   " + firstStr[i - 1];
            }
        }

        solution[0][0] = "NONE";

        for (int i = 1; i <= firstStr.length; i++) {
            for (int j = 1; j <= secondStr.length; j++) {
                if (firstStr[i - 1] == secondStr[j - 1] && firstStr[i - 1] != SEPARATOR) {
                    LCS[i][j] = LCS[i - 1][j - 1] + 1;
                    solution[i][j] = "diag";
                } else {
                    LCS[i][j] = 0;
                    solution[i][j] = "none";
                }
                if(LCS[i][j] > max) {
                    max = LCS[i][j];
                    maxI = i;
                    maxJ = j;
                }
            }
        }

        System.out.println("Path values:");
        for (int i = 0; i <= firstStr.length; i++) {
            for (int j = 0; j <= secondStr.length; j++) {
                System.out.print(" " + LCS[i][j]);
            }
            System.out.println();
        }

        System.out.println();
        System.out.println("Path recovery:");
        for (int i = 0; i <= firstStr.length; i++) {
            for (int j = 0; j <= secondStr.length; j++) {
                System.out.print(" " + solution[i][j]);
            }
            System.out.println();
        }
        System.out.println();
        System.out.println("max:" + max + " maxI:" + maxI + " maxJ:" + maxJ);

        return printSolution(maxI, maxJ);
    }

    public String printSolution(int i, int j) {
        String answer = "";
        while(i - 1 >= 0 && j - 1 >= 0 && LCS[i][j] != 0) {
            answer = firstStr[i - 1] + answer;
            i--;
            j--;
        }
        System.out.println("Current max solution: " + answer);
        return answer;
    }

    public static void main(String[] args) {
        String firstStr = "x4.printString(\\\"Bianca.()\\\").y1();";
        String secondStr = "sb.printString(\\\"Bianca.()\\\").length();";
        String maxSubstr;
        LongestCommonSequence lcs;
        do {
            lcs = new LongestCommonSequence(firstStr.toCharArray(), secondStr.toCharArray());
            maxSubstr = lcs.find();
            if(maxSubstr.length() != 0) {
                firstStr = firstStr.replace(maxSubstr, "" + LongestCommonSequence.SEPARATOR);
                secondStr = secondStr.replace(maxSubstr, "" + LongestCommonSequence.SEPARATOR);
            }
        }
        while(maxSubstr.length() != 0);

        System.out.println();
        System.out.println("first:" + firstStr + " second: " + secondStr);

        System.out.println("First array: ");
        String[] firstArray = firstStr.split("\\" + SEPARATOR);
        String[] secondArray = secondStr.split("\\" + SEPARATOR);
        for(String s: firstArray) {
            System.out.println(s);
        }
        System.out.println();
        System.out.println("Second array: ");
        for(String s: secondArray) {
            System.out.println(s);
        }
    }
}

- aUserHimself

---

我正在尝试应用“最长公共子序列”来实现我的目标。 - delca85

Answer 3

我的代码可能不是最紧凑的，但我为了清晰度而这样编写:

public static void main(String[] args) throws InterruptedException, FileNotFoundException, ExecutionException {

    String s1 = "x4.printString(\"Bianca.()\").y1();";
    String s2 = "sb.printString(\"Bianca.()\").length();";

    List<String> result = new ArrayList<>();
    result.addAll(getDifferences(s1, s2));
    result.addAll(getDifferences(s2, s1));

    System.out.println(result);
}

public static List<String> getDifferences(String s1, String s2){
    if(s1 == null){
        return Collections.singletonList(s2);
    }
    if(s2 == null){
        return Collections.singletonList(s1);
    }
    int minimalLength = Math.min(s1.length(),s2.length());
    List<String> result = new ArrayList<>();
    StringBuilder buffer = new StringBuilder(); // keep the consecutive differences
    for(int i = 0; i<minimalLength; i++ ){
        char c = s1.charAt(i);
        if(c == s2.charAt(i)){
            if( buffer.length() > 0){
                result.add(buffer.toString());
                buffer = new StringBuilder();
            }
        } else {
            buffer.append(c);
        }
    }
    if(s1.length() > minimalLength){
        buffer.append(s1.substring(minimalLength)); // add the rest
    }
    if(buffer.length() > 0){
        result.add(buffer.toString()); //flush buffer
    }
    return result;
}

然而，请注意，由于您没有指定要删除非单词字符，因此也会返回这些字符（但它们不会出现在您期望的输出中）。

- Jeremy Grand

---

啊，我可能误解了。您认为“();”仍然相等，而不考虑它们的索引。这可能会改变实现方式。 - Jeremy Grand

Answer 4

这是我找到的解决方案，感谢@aUserHimself发布的this链接。

private static int[][] lcs(String s, String t) {
        int m, n;
        m = s.length();
        n = t.length();
        int[][] table = new int[m+1][n+1];
        for (int i=0; i < m+1; i++)
            for (int j=0; j<n+1; j++)
                table[i][j] = 0;
        for (int i = 1; i < m+1; i++)
            for (int j = 1; j < n+1; j++)
                if (s.charAt(i-1) == t.charAt(j-1))
                        table[i][j] = table[i-1][j-1] + 1;
                else
                    table[i][j] = Math.max(table[i][j-1], table[i-1][j]);
        return table;
    }

private static List<List<String>> getDiffs(int[][] table, String s, String t, int i, int j,
                                           int indexS, int indexT, List<List<String>> diffs){
    List<String> sList, tList;
    sList = diffs.get(0);
    tList = diffs.get(1);
    if (i > 0 && j > 0 && (s.charAt(i-1) == t.charAt(j-1)))
        return getDiffs(table, s, t, i-1, j-1, indexS, indexT, diffs);
    else if (i > 0 || j > 0) {
            if (i > 0 && (j == 0 || table[i][j-1] < table[i-1][j])){
                if (i == indexS)
                    sList.set(sList.size()-1, String.valueOf(s.charAt(i-1)) + sList.get(sList.size() - 1));
                else
                    sList.add(String.valueOf(s.charAt(i-1)));
                diffs.set(0, sList);
                return getDiffs(table, s, t, i-1, j, i-1, indexT, diffs);
            }
            else if (j > 0 && (i == 0 || table[i][j-1] >= table[i-1][j])){
                if (j == indexT)
                    tList.set(tList.size() - 1, String.valueOf(t.charAt(j-1)) + tList.get(tList.size()-1));
                else
                    tList.add(String.valueOf(t.charAt(j-1)));
                diffs.set(1, tList);
                return getDiffs(table, s, t, i, j-1, indexS, j-1, diffs);
            }
        }
    return diffs;
}

private static List<List<String>> getAllDiffs(String s, String t){
    List<List<String>> diffs = new ArrayList<List<String>>();
    List<String> l1, l2;
    l1 = new ArrayList<>();
    l2 = new ArrayList<>();
    diffs.add(l1);
    diffs.add(l2);
    return getDiffs(lcs(s, t), s, t, s.length(), t.length(), 0,  0, diffs);
}

我发帖是因为或许对某些人来说会很有趣。

- delca85