计算最长公共子序列

今天药忘吃喽~ 2022-05-14 05:48 29阅读 0赞

# 前言 #

什么是最长公共子序列呢?好比一个数列 S，如果分别是两个或多个已知数列的子序列，且是所有符合此条件序列中最长的，则S 称为已知序列的最长公共子序列。

# 如何解决 #

通用的解法用动态规划，如何使用动态规划解题，晚上已经有很多不同人的答案了，推荐几个：  
[程序员编程艺术第十一章：最长公共子序列(LCS)问题][LCS]  
[算法导论—–最长公共子序列LCS（动态规划）][LCS 1]

# 我的代码 #

# c语言 #

#include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    
    #define N 10005
    
    int dp[N][N];
    int b[N][N];
    
    void lcs(const char* s1, const char* s2)
    {
            int len_s1 = strlen(s1);
            int len_s2 = strlen(s2);
            for (int i = 0; i <= len_s1; i++)
            {
                    dp[i][0] = 0;
            }
            for (int j = 0; j <= len_s2; j++)
            {
                    dp[0][j] = 0;
            }
            for (int i = 1; i <= len_s1; i++)
            {
                    for (int j = 1; j <= len_s2; j++)
                    {
                            if (s1[i - 1] == s2[j - 1])
                            {
                                    dp[i][j] += dp[i - 1][j - 1] + 1;
                                    b[i][j] = 1;
                            }
                            else if (dp[i - 1][j] >= dp[i][j - 1])
                            {
                                    dp[i][j] = dp[i - 1][j];
                                    b[i][j] = 3; // 取上一层
                            }
                            else
                            {
                                    dp[i][j] = dp[i][j - 1];
                                    b[i][j] = 2; //取左一列
                            }
                    }
            }
    }
    
    
    void print_lcs(const char* x, int i, int j)
    {
            if (i == 0 || j == 0)
            {
                    return ;
            }
            if (b[i][j] == 1)
            {
                    print_lcs(x, i - 1, j - 1);
                    printf("%c", x[i - 1]);
            }
            else if (b[i][j] == 3)
            {
                    print_lcs(x, i - 1, j);
            }
            else
            {
                    print_lcs(x, i, j - 1);
            }
    }
    
    
    
    int main()
    {
            //const char *s1 = "ABCBDAB";
            //const char *s2 = "BDCABA";
            char s1[100], s2[100];
            scanf("%s", s1);
            scanf("%s", s2);
            int len_s1 = strlen(s1);
            int len_s2 = strlen(s2);
            lcs(s1, s2);
            print_lcs(s1, len_s1, len_s2);
            printf("\n");
            return 0;
    }

## python ##

#!/bin/python
    
    
    import sys,os
    
    
    res = []
    def lcs(str1, str2):
        len_str1 = len(str1)
        len_str2 = len(str2)
        dp = [[0] * (len_str2+1) for _ in range(len_str1+1)]
        b = [[0] * (len_str2+1) for _ in range(len_str1+1)]
        for i in range(1, len_str1 + 1):
            for j in range(1, len_str2 + 1):
                if str1[i - 1] == str2[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1] + 1
                    b[i][j] = 1
                elif dp[i-1][j] >= dp[i][j - 1]:
                    dp[i][j] = dp[i - 1][j]
                    b[i][j] = 3
                else:
                    dp[i][j] = dp[i][j - 1]
                    b[i][j] = 2
        return b
    
    def print_lcs(str1, b, i, j):
        if i == 0 or j == 0:
            return
        if b[i][j] == 1:
            print_lcs(str1, b, i - 1, j - 1)
            res.append(str1[i - 1])
        elif b[i][j] == 3:
            print_lcs(str1, b, i - 1, j)
        else:
            print_lcs(str1, b, i, j - 1)
    
    
    def main():
        str1 = sys.stdin.readline().strip()
        str2 = sys.stdin.readline().strip()
        #print(str1, str2)
        b = lcs(str1, str2)
        #print(b)
        print_lcs(str1, b, len(str1), len(str2))
        print(''.join(res))
    
    
    if __name__ == '__main__':
        main()

## 测试 ##

ABCBDAB
    BDCABA
    
    
    res:
    BCBA

[LCS]: https://blog.csdn.net/v_july_v/article/details/6695482
[LCS 1]: https://blog.csdn.net/so_geili/article/details/53737001