最长公共子串和最长公共子序列

最长公共子串

参考链接：https://blog.csdn.net/weixin_42735784/article/details/88405516

动态规划法：
定义字符串str1的索引为i, 第二个字符串str2的索引为j
定义dp[i][j] 为str1取前面长度为i的子串，str2取前面长度为j的子串，str1必须以第i个结果，str2必须以第j个结果
定义状态转移方程

原理：如果2个字符串的最后一个不相等，它们的LCS=空串， 若相等，2个都往前推一位，该情况的子串+这一位=现在的子串
特别注意：比如对于str1, 前i个： 索引是从0到i - 1

public int longestCommonSubstring(String A, String B) {
        int a_len = A.length();
        int b_len = B.length();
        int max = 0;
        //dp[i][j] 为 A取前i个，B取前j个，看这两个的LCS长度，各个的最后一个不等，肯定是0了
        int[][] dp = new int[a_len + 1][b_len + 1];  

        int max = 0;
        for (int i = 1; i <= a_len; ++i) {
            for (int j = 1; j <= b_len; ++j) {
                if (A.charAt(i - 1) == B.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    if(dp[i][j] > max){
                        max = dp[i][j];
                    }
                } else {
                    dp[i][j] = 0;
                }
            }
        }

        return max;
    }

最长公共子序列

和最长公共子串的区别在于状态转移方程：当A[i]!=B[j]时dp[i][j] = Max(dp[i-1][j],dp[i][j-1])

public int longestCommonSubstring(String A, String B) {
        int a_len = A.length();
        int b_len = B.length();
        int max = 0;
        //dp[i][j] 为 A取前i个，B取前j个，看这两个的LCS长度，各个的最后一个不等，肯定是0了
        int[][] dp = new int[a_len + 1][b_len + 1];  

        for (int i = 1; i <= a_len; ++i) {
            for (int j = 1; j <= b_len; ++j) {
                if (A.charAt(i - 1) == B.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    //两个之间的区别
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[a_len][b_len];
    }


public String LCS (String s1, String s2) {
        // write code here
       int str1Len = s1.length();
        int str2Len = s2.length();
        int[][] cLenNUm = new int[s1.length() + 1][s2.length() + 1];//默认赋值，[0][?],[?][0]默认两侧皆0,类似公式中0的场景
        //构造一个LCS长度数组
        for (int i = 1; i <= str1Len; i++) {
            for (int j = 1; j <= str2Len; j++) {
                if (s1.charAt(i - 1) == s2.charAt(j - 1)) {//对应公式第二条相等
                    cLenNUm[i][j] = cLenNUm[i - 1][j - 1] + 1;
                } else {//对应公式第三条不相等
                    cLenNUm[i][j] = Math.max(cLenNUm[i][j - 1], cLenNUm[i - 1][j]);
                }
            }
        }

        //反推结果
        int i = str1Len;
        int j = str2Len;
        StringBuffer sb = new StringBuffer();//作为结果
        while (i > 0 && j > 0) {//这里其实处理了i=0,j=0的，对应公式0的反推场景
            if (s1.charAt(i - 1) == s2.charAt(j - 1)) {//反推公式中不相等的场景
                //该值一定是被选取到的，根据之前的公式，知道两条字符串的下标都前进一位
                sb.append(s1.charAt(i - 1));
                i--;
                j--;
            } else {//对应公式中不相等的反推场景
                if (cLenNUm[i][j - 1] > cLenNUm[i - 1][j]) {//找大的那个方向，此处是左边大于上面，则该处的结果是来自左边
                    j--;
                } else if (cLenNUm[i][j - 1] < cLenNUm[i - 1][j]) {
                    i--;
                } else if (cLenNUm[i][j - 1] == cLenNUm[i - 1][j]) {
                    //对于有分支的可能时，我们选取单方向
                    j--;   //此结果对于结果1所选取方向，str1的下标左移一位.替换为j--，则结果对应与结果2选取的方向
                }
            }
        }
        //由于是从后往前加入字符的，需要反转才能得到正确结果
        return sb.reverse().toString();
    }