Java基于动态规划法实现求最长公共子序列及最长公共子字符串示例

Java基于动态规划法实现求最长公共子序列及最长公共子字符串示例攻略

什么是最长公共子序列？

两个序列 X 和 Y 的“公共子序列”，是指存在一个序列 Z，Z 中元素既在 X 中，也在 Y 中，在 X 和 Y 中出现的次序分别相同，且 Z 的长度最大。例如序列“12345”和“1245”的公共子序列有“12”、“145”等，其中“145”最长，长度为 3，即为“12345”和“1245”的最长公共子序列（Largest Common Subsequence，LCS）。

什么是最长公共子串？

两个字符串 X 和 Y 的“公共子串”，是指在 X 和 Y 中都出现过的连续字符串。例如字符串“Hello World”和“Hella World”的公共子串有“Hell”、“ello”等，其中“ello”最长，长度为 4，即为“Hello World”和“Hella World”的最长公共子串（Longest Common Substring，LCS）。

如何求最长公共子序列？

我们可以利用动态规划（Dynamic Programming，DP）来解决这个问题。

动态规划法解决问题的一般步骤：

1. 问题转化：将原问题转化为子问题。
2. 定义状态：定义状态方程。
3. 确定状态转移方程：根据子问题之间的关系，确定通项公式。
4. 分析复杂性：定义好状态和状态转移方程后，问题的时间复杂度通常比较容易分析。

最长公共子序列-算法分析

众所周知，两个序列的最长公共子序列问题可以用动态规划算法求解。具体思想是，设序列 X 和 Y 的长度分别为 m 和 n，则先用 m 行 n 列的矩阵 dp 存储 X 和 Y 之间任意部分的 LCS 长度，其中 dp[i][j] 表示 X[0~i] 和 Y[0~j] 的 LCS 的长度。接下来，序列X和Y的任何LCS都是矩阵 dp[m][n] 中的数字。

例如，X = “fasdugnisarefhadseo” ，Y = “sduguarsdewq” ，LCS 就是 “sdug”，长度为 4。

实现如下：

public static String LCSLength(String str1, String str2) throws Exception {
        if (str1.isEmpty() || str2.isEmpty()){
            throw new Exception("cannot input null...");
        }

        int len1 = str1.length();
        int len2 = str2.length();
        int[][] LCSLength = new int[len1 + 1][len2 + 1];

        for (int i = 0; i <= len1; i++) {
            for (int j = 0; j <= len2; j++) {
                if (i == 0 || j == 0) {
                    LCSLength[i][j] = 0;
                } else if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                    LCSLength[i][j] = LCSLength[i - 1][j - 1] + 1;
                } else {
                    LCSLength[i][j] = Math.max(LCSLength[i - 1][j], LCSLength[i][j - 1]);
                }
            }
        }

        int index = LCSLength[len1][len2];
        char[] lcs = new char[index];
        int i = len1, j = len2;
        while (i > 0 && j > 0) {
            if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                lcs[--index] = str1.charAt(i - 1);
                i--;
                j--;
            } else if (LCSLength[i - 1][j] > LCSLength[i][j - 1]) {
                i--;
            } else {
                j--;
            }
        }
        return new String(lcs);
    }

最长公共子串-算法分析

在实现最长公共子串的时候，我们需要将问题转化为动态规划问题。我们需要用矩阵 dp 记录当前考虑的任意两个子串的最长公共子串长度，其中 dp[i][j] 表示 str1 的前 i 个字符和 str2 的前 j 个字符的最长公共子串长度。由于最长公共子串要求连续，所以在考虑 str1 和 str2 的第 i 个和第 j 个字符的时候，我们如果两者相等，就可以根据 dp[i - 1][j - 1] + 1 更新当前的 dp[i][j]，否则 dp[i][j] = 0。

例如，str1 = “fasdugnisarefhadseo” ，str2 = “sduguarsdewq” ，LCS 就是 “sdug”，长度为 4。

实现如下：

class Main {
    public static String LCSubstring(String str1, String str2) throws Exception {
        if (str1.isEmpty() || str2.isEmpty()){
            throw new Exception("cannot input null...");
        }
        int[][] dp = new int[str1.length() + 1][str2.length() + 1];
        int maxLen = 0, maxEnd = str1.length(), index = str1.length();
        for (int i = 1; i <= str1.length(); i++) {
            for (int j = 1; j <= str2.length(); j++) {
                if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }
                if (dp[i][j] > maxLen) {
                    maxLen = dp[i][j];
                    maxEnd = i;
                }
            }
        }
        return str1.substring(maxEnd - maxLen, maxEnd);
    }
}

示例说明

示例 1：求两个字符串的最长公共子序列

输入：

String str1 = "fasdugnisarefhadseo";
String str2 = "sduguarsdewq";
String lcs = LCSLength(str1, str2);
System.out.println(lcs);

输出：

sdug

示例 2：求两个字符串的最长公共子串

输入：

String str1 = "fasdugnisarefhadseo";
String str2 = "sduguarsdewq";
String lcs = LCSubstring(str1, str2);
System.out.println(lcs);

输出：

sdug

总结

以上就是动态规划求解最长公共子序列和最长公共子串的完整攻略，其中给出了两个示例分别演示了如何使用代码求解最长公共子序列和最长公共子串。在实际编程中，我们可以利用动态规划算法解决这个问题，使用矩阵 dp 记录当前问题的状态和解，用通用公式进行状态转移，从而得出最优解。