最长公共子序列

简介: 问题描述子序列 X=(ABCBDAB) X的子序列是下标递增的X的字符组成的序列,但是不一定连续,如:ABCD,ACDAB等都是其子序列,而 ADC不是子序列最长公共子序列 如果Z既是X的子序列,又是Y的子...

问题描述

  • 子序列
    X=(ABCBDAB) X的子序列是下标递增的X的字符组成的序列,但是不一定连续,如:ABCD,ACDAB等都是其子序列,而 ADC不是子序列
  • 最长公共子序列
    如果Z既是X的子序列,又是Y的子序列,那么Z是X与Y的公共子序列,其中最长Z就是最长公共子序列
  • 序列相似度
    该问题用来描述两个序列的相似度,当然相似度还有其他描述方法
    • X是Y的子串
    • X转换为Y的操作最少
    • X与Y的最大公共字串

求解

暴力求解

分别求出X,Y的所有子序列,然后求所有公共子序列,取其中长度最大的,由于求所有自序列复杂度为2^m,时间复杂度为指数型

动态规划

原理:
X={x1,x2...xn}
Y={y1,y2...ym}
他们最长公共子序列为Z
如果 xm=yn,则Zk=xm=yn,Zk-1Xm-1Yn-1的最长公共子序列
如果xm!=yn,若Zk!=xm,则ZXm-1Yn的最大公共子序列
如果xm!=yn,若Zk!=yn,则ZXmYn-1的最大公共子序列

代码

  • 如果只求长度,可以用一维数组迭代求解
  • 如果求具体序列,需要用二维数组来记录求解路径
public class LongestCommonSequence {
    public static void main(String[] args) {
        String X = "ACCGGTCGAGTGCGCGGAAGCCGGCCGAA";
        String Y = "GTCGTTCGGAATGCCGTTGCTCTGTAAA";
        String C = "GTCGTCGGAAGCCGGCCGAA";
        System.out.println(longestCommonSequence(X, Y).equals(C));
        System.out.println(longestCommonSequenceLength(X, Y));
    }
    public static int longestCommonSequenceLength(String X, String Y) {
        int m = X.length();
        int n = Y.length();
        int[] c = new int[m + 1];
        for (int i = 0; i <= m; i++) {
            c[i] = 0;
        }
        for (int i = 1; i <= n; i++) {
            int leftUp = 0;
            for (int j = 1; j <= m; j++) {
                int temp = leftUp;
                leftUp = c[j];
                if (X.charAt(j - 1) == Y.charAt(i - 1)) {
                    c[j] = temp + 1;
                } else {
                    c[j] = Math.max(c[j - 1], c[j]);
                }
            }
        }
        return c[m];
    }
    public static String longestCommonSequence(String X, String Y) {
        int m = X.length();
        int n = Y.length();
        int[][] c = new int[m + 1][n + 1];
        for (int i = 0; i <= m; i++) {
            c[i][0] = 0;
        }
        for (int i = 0; i <= n; i++) {
            c[0][i] = 0;
        }
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (X.charAt(i - 1) == Y.charAt(j - 1)) {
                    c[i][j] = c[i - 1][j - 1] + 1;
                } else {
                    c[i][j] = Math.max(c[i - 1][j], c[i][j - 1]);
                }
            }
        }
        StringBuilder sb = new StringBuilder();
        while (m > 0 && n > 0) {
            if (X.charAt(m - 1) == Y.charAt(n - 1)) {
                sb.append(X.charAt(m - 1));
                m--;
                n--;
            } else if (c[m - 1][n] >= c[m][n - 1]) {
                m--;
            } else {
                n--;
            }
        }
        return sb.reverse().toString();
    }
}
目录
相关文章
|
6月前
|
存储
最长公共子序列(LCS)
最长公共子序列(LCS) “【5月更文挑战第21天】”
81 2
|
1月前
|
机器学习/深度学习 人工智能 算法
【算法】最长公共子序列(C/C++)
【算法】最长公共子序列(C/C++)
|
6月前
leetcode-1143:最长公共子序列
leetcode-1143:最长公共子序列
57 0
1265:【例9.9】最长公共子序列 2021-01-15
1265:【例9.9】最长公共子序列 2021-01-15
leetcode 1143 最长的公共子序列
leetcode 1143 最长的公共子序列
92 0
leetcode 1143 最长的公共子序列
力扣1143. 最长公共子序列 动态规划之最长公共子序列
力扣1143. 最长公共子序列 动态规划之最长公共子序列
191 0
力扣1143. 最长公共子序列 动态规划之最长公共子序列
|
测试技术
最长公共子序列(LeetCode-1143)
最长公共子序列(LeetCode-1143)
110 0
最长公共子序列(LeetCode-1143)
最长公共子序列(一 | 计算长度版)
最长公共子序列(一 | 计算长度版)
|
算法 BI
最长公共子序列(三 | 存在多个解的情况)
最长公共子序列(三 | 存在多个解的情况)