Java实现最长公共子序列算法 (LCS) - 动态规划法

Java实现最长公共子序列算法 (LCS) - 动态规划法

在生物信息学中，经常需要比较两个或多个DNA序列的相似程度。DNA是由碱基分子组成的串。这些碱基是腺嘌呤(adenine)、鸟嘌呤(guanine)、胞嘧啶(cytosine) 和胸腺嘧啶(thymine)，常常用它们对应英文单词的第一个字母表示，分别为A、G、C 和T。例如，一种组织的DNA序列为S1='ACCGGTCGAGTGCGCGGAAGCCGGCCGAA'，而另一种组织的序列为S2='GTCGTTCGGAATGCCGTTGCTCTGTAAA'。

度量相似性常用的方法之一是，若存在串S3，且S3中的碱基以相同顺序出现在S1和S2中（不必是连续），S3越长，则串S1与S2的相似性越大。在我们所给出的例子中。S3='GTCGTCGGAAGCCGGCCGAA'。

本文将使用动态规划法求两个字符串的最长公共子序列的函数。

算法思路

动态规划，设dp[i][j]表示S1[0...i-1]和S2[0...j-1]的最长公共子序列的长度，则有：

1. 初始状态:
   • dp[i][j] = 0 (i=0 or j=0)
2. 状态转移:
   • dp[i][j] = dp[i-1][j-1] + 1 (S1[i-1] == S2[j-1])
   • dp[i][j] = max(dp[i-1][j], dp[i][j-1]) (S1[i-1] != S2[j-1])

最后根据dp数组反推出最长公共子序列。

时间复杂度

O(mn)，其中m和n分别为S1和S2的长度。

代码实现

class CommonOrder {
    static StringBuffer s1;// save string1
    static StringBuffer s2;// save string2
    static StringBuffer s3;// save commom string   
    CommonOrder(String str1,String str2)
    {
        s1=new StringBuffer(str1);
        s2=new StringBuffer(str2);
        s3=new StringBuffer();
    }        
    void subsequenceOrder() {
        int m = s1.length();
        int n = s2.length();
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (s1.charAt(i - 1) == s2.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]);
                }
            }
        }
        int i = m, j = n;
        while (i > 0 && j > 0) {
            if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                s3.insert(0, s1.charAt(i - 1));
                i--;
                j--;
            } else {
                if (dp[i - 1][j] > dp[i][j - 1]) {
                    i--;
                } else {
                    j--;
                }
            }
        }
    }
    StringBuffer getCommonString(){
        return s3;
    }
}

public class Main{
    public static void main(String[] args) {
       String X = null,Y = null;       
       Scanner sc=new Scanner(System.in);       
       if(sc.hasNext()) X=sc.nextLine();
       if(sc.hasNext()) Y=sc.nextLine();
       CommonOrder co=new CommonOrder(X,Y);
       co.subsequenceOrder();
       StringBuffer str=co.getCommonString();
       System.out.println(str+' '+str.length());
    }
}

输入样例

abcbdabc
acbbdabdbcb

输出样例

acbdabc 7

代码解释

1. 初始化dp数组: dp数组用于存储每个子问题的最优解，dp[i][j] 表示 S1 的前 i 个字符和 S2 的前 j 个字符的最长公共子序列长度。
2. 填充dp数组: 遍历 S1 和 S2 的所有字符，根据状态转移方程填充dp数组。
3. 反推出最长公共子序列: 从 dp 数组的右下角开始，根据 dp 的值回溯，找到最长公共子序列，并存储在 s3 中。

总结

本文详细介绍了使用Java实现最长公共子序列算法 (LCS) 的方法，并提供了示例代码和解释。动态规划法是解决此类问题的有效方法，可以有效地计算最长公共子序列。