最长公共子串（Longest Common Substring）和最长公共子序列（Longest Common Subsequence）

参考文章：https://blog.csdn.net/u013309870/article/details/69479488

最长公共子串（Longest Common Substring）

/**
     * 要求：求两个字符串的最长公共子串，如text1="12345abc"，text2="2d3e45fabc"，则二者的最长公共子串为"abc"
     * @param text1 字符串1，String类型
     * @param text2 字符串2，String类型
     * @return 公共字串，String类型；稍加修改就能返回长度
     * 方法：动态规划，填表，text1为纵轴，text2为横轴，dp[i][j]表示text1的前i个字符和text2的前j个字符的最大公共子串长度
     * 计算dp[i][j] 的步骤如下：
     * ①矩阵dp的第一列 dp[0…m-1][0].对于 某个位置（i，0）如果text1[i]==text2[0],则dp[i][0]=1,否则dp[i][0]=0
     * ②矩阵 dp 的第一行 dp[0][0…n-1].对于 某个位置（0，j）如果text1[0]==text2[j],则dp[0][j]=1,否则dp[0][j]=0
     * ③其他位置从左到右从上到下计算，dp[i][j]的值只有两种情况：
     * 1). text1[i]==text2[j],dp[i][j]=dp[i-1][j-1]+1;
     * 2). text1[i]!=text2[j]则dp[i][j]=0;
     * 这里dp[i][j]表示以j（i也一样）下标对应的字符为公共子串结尾的子串的长度，如果不是子串结尾即text1[i]!=text2[j]，则dp[i][j]=0
     */
    public static String longestCommonSubString(String text1, String text2) {
        if (text1 == null || text2 == null || text1.length() == 0 || text2.length() == 0) {
            return "";
        }
        // 动态规划数组dp，行数为text1的长度，列数为text2的长度
        int[][] dp = new int[text1.length()][text2.length()];
        // 字串的最大长度
        int max = 0;
        // 记录公共子串最后一个字符在text1中的位置
        int index = -1;
        // 初始化dp的首列
        for (int i = 0; i < text1.length(); i++) {
            if (text2.charAt(0) == text1.charAt(i)) {
                dp[i][0] = 1;
            } else {
                dp[i][0] = 0;
            }
            // text1.charAt(0) == text2.charAt(i) ? dp[i][0] = 1 : dp[i][0] = 0;
        }
        // 初始化dp的首行
        for (int i = 0; i < text2.length(); i++) {
            if (text1.charAt(0) == text2.charAt(i)) {
                dp[0][i] = 1;
            } else {
                dp[0][i] = 0;
            }
        }
        // 填表，补充动态规划数组
        for (int i = 1; i < text1.length(); i++) {
            for (int j = 1; j < text2.length(); j++) {
                if (text1.charAt(i) == text2.charAt(j)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    // 记录最大长度
                    max = Math.max(max, dp[i][j]);
                    // 记录位置
                    index = i;
                }else {
                    dp[i][j] = 0;
                }
            }
        }
        return index != -1 ? text1.substring(index + 1 - max, index + 1) : "";
    }

最长公共子序列（Longest Common Subsequence）

/**
     * 要求：给定两个字符串text1 和text2，返回这两个字符串的最长公共子序列的长度。
     * 一个字符串的子序列是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
     * 例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。
     * 若这两个字符串没有公共子序列，则返回 0。
     * @param text1 字符串1，String类型
     * @param text2 字符串2，String类型
     * @return 子序列的长度，如果不存在则返回0，int类型
     * 方法：动态规划，填表，text1为纵轴，text2为横轴，dp[i][j]表示text1的前i个字符和text2的前j个字符的最大公共子序列长度
     * 计算dp[i][j] 的步骤如下：
     * ①矩阵dp的第一列 dp[0…m-1][0].对于 某个位置（i，0）如果text1[i]==text2[0],则dp[i][0]=1,否则dp[i][0]=0
     * ②矩阵 dp 的第一行 dp[0][0…n-1].对于 某个位置（0，j）如果text1[0]==text2[j],则dp[0][j]=1,否则dp[0][j]=0
     * ③其他位置从左到右从上到下计算，dp[i][j]的值只有两种情况：
     * 1). text1[i]==text2[j],dp[i][j]=dp[i-1][j-1]+1;
     * 2). text1[i]!=text2[j]则dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
     * 最后，dp[text1.length][text2.length]即为所求
     */
    public static int longestCommonSubsequence(String text1, String text2) {
        if (text1 == null || text2 == null || text1.length() == 0 || text2.length() == 0) {
            return 0;
        }
        // 动态规划数组dp，行数为text1的长度加1，列数为text2的长度加1，方便计算
        int[][] dp = new int[text1.length() + 1][text2.length() + 1];
        // 填表，补充动态规划数组，行和列的初始化包含在里面
        for (int i = 1; i <= text1.length(); i++) {
            for (int j = 1; j <= text2.length(); j++) {
                if (text1.charAt(i-1) == text2.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]);
                }
            }
        }
        // dp数组的最右下角的元素值即为结果值
        return dp[text1.length()][text2.length()];
    }