数据结构 - 字符串 - 最长公共子序列 + 最长公共子字符串 - 动态规划

谁践踏了优雅 2022-06-01 02:42 187阅读 0赞

### 最长公共子序列 ###

![最长公共子序列][SouthEast]

/**
     * 最长公共子序列
     * 参考链接：http://blog.csdn.net/biangren/article/details/8038605
     * Created by 18710 on 2017/8/24.
     */
    public class LongestCommonSubsequence {
        
    
        public static void main(String[] args) {
            char[] x = {
       'A', 'B', 'C', 'B', 'D', 'A', 'B'};
            char[] y = { 'B', 'D', 'C', 'A', 'B', 'A'};
            int[][] direction = getLongestCommonSubsequence(x, y);
            getLongestCommonSubsequence(direction, x, x.length - 1, y.length - 1);
        }
    
        /**
         * 动态规划：状态为目前的最长子序列长度
         * lcs[i][j] = 0; if i == 0 || j == 0
         * lcs[i][j] = lcs[i-1][j-1] + 1; if x[i]=y[j]
         * lcs[i][j] = lcs[i][j-1]; if x[i]!=y[j] && lcs[i][j-1] > lcs[i-1][j]
         * lcs[i][j] = lcs[i-1][j]; if x[i]!=y[j] && lcs[i][j-1] < lcs[i-1][j]
         * 具体流程参考 img文件夹下的 LongestCommonSubsequence.img
         * @param x 第一个字符串
         * @param y 第二个字符串
         * @return 最长子序列的遍历方向
         */
        public static int[][] getLongestCommonSubsequence(char[] x, char[] y) {
            if (x == null || y == null || x.length == 0 || y.length == 0) {
                return null;
            }
    
            // 长度为原来的长度加1，因为第一行和第一列的值都是空，这样动态规划的时候省去判断第一行然后i-0小于0的情况
            int[][] lcs = new int[x.length + 1][y.length + 1]; // 保存最长子序列的长度
            int[][] direction = new int[x.length + 1][y.length + 1]; // 保存搜索方向
    
            for (int i = 0; i < x.length; i++) {
                for (int j = 0; j < y.length; j++) {
                    if (x[i] == y[j]) {
                        lcs[i + 1][j + 1] = lcs[i][j] + 1; // 相等公共子序列长度加1
                        direction[i + 1][j + 1] = 1; // 1表示左上角对角线移动
                    } else if (lcs[i][j + 1] >= lcs[i + 1][j]) { /** 注意条件是大于等于*/
                        lcs[i + 1][j + 1] = lcs[i][j + 1]; // 上边的元素值较大
                        direction[i + 1][j + 1] = 0; // 0表示上移动
                    } else {
                        lcs[i + 1][j + 1] = lcs[i + 1][j];  // 左边的元素值较大
                        direction[i + 1][j + 1] = -1; // -1表示左移动
                    }
                }
            }
            return direction;
        }
    
        /**
         *根据最长子序列的方向打印子序列
         * @param direction 方向数组
         * @param x 第一个或者第二个字符串
         * @param i 横坐标
         * @param j 纵坐标
         */
        public static void getLongestCommonSubsequence (int[][] direction, char[] x, int i, int j) {
            if (i < 0 || j < 0) { // 第一行为空
                return ;
            }
            if (direction[i + 1][j + 1] == 1) { // 1表示左上角
                getLongestCommonSubsequence(direction, x, i - 1, j - 1);
                System.out.print(x[i] + " ");
            } else if (direction[i + 1][j + 1] == 0) { // 0表示上移动
                getLongestCommonSubsequence(direction, x, i - 1, j);
            } else if (direction[i + 1][j + 1] == -1){ // -1表示左移动
                getLongestCommonSubsequence(direction, x, i, j - 1);
            }
        }
    
    }

### 最长公共子串 ###

动态规划：求得最长子串长度和最后一个相同字符的下标即可

/**
     * 最长公共子串
     * 动态规划：求的最长子串长度和最后一个相同字符的下标即可
     * 参考链接：http://blog.csdn.net/hackbuteer1/article/details/6686931
     *
     * Created by 18710 on 2017/8/24.
     */
    public class LongestCommonSubstring {
        
    
        public static void main(String[] args) {
            char[] x = {
       'A', 'B', 'C', 'D',};
            char[] y = { 'C', 'A', 'B', 'E'};
            getLongestCommonSubstring(x, y);
        }
    
        /**
         * 动态规划：状态为目前的最长子串长度
         * lcs[i][j] = 0; if i == 0 || j == 0 || x[i]!=y[j]
         * lcs[i][j] = lcs[i-1][j-1] + 1; if x[i]=y[j]
         * @param x 第一个字符串
         * @param y 第二个字符串
         * @return
         */
        public static void getLongestCommonSubstring(char[] x, char[] y) {
            if (x == null || y == null || x.length == 0 || y.length == 0) {
                return ;
            }
            int max = 0; // 最长公共子串的长度
            int lastX = 0; // 第一个字符串 最长公共子串最后一个字符的数组下标
            // 长度为原来的长度加1，因为第一行和第一列的值都是空，
            // 这样动态规划的时候省去判断第一行然后i-0小于0的情况
            int[][] lcs = new int[x.length + 1][y.length + 1]; // 保存最长子序列的长度
    
            for (int i = 0; i < x.length; i++) {
                for (int j = 0; j < y.length; j++) {
                    if (x[i] == y[j]) {
                        lcs[i + 1][j + 1] = lcs[i][j] + 1; // 相等公共子序列长度加1
                    } else {
                        lcs[i + 1][j + 1] = 0;  // 左边的元素值较大
                    }
                    if (lcs[i + 1][j + 1] > max) { // 更新最长子串的长度和两个子串对应的下标
                        max = lcs[i + 1][j + 1];
                        lastX = i;
                    }
                }
            }
            System.out.println("最长子串长度为：" + max + ",下标为：" + lastX);
            StringBuffer sb = new StringBuffer(); // 保存最长公共子串
            while (max-- > 0) {
                sb.append(x[lastX--]);
            }
            System.out.println(sb.reverse().toString()); // 逆序打印
        }
    
    }

[SouthEast]: /images/20220601/ae6b6b4dedd840f195e833d3f1791c8e.png