最长公共子序列(DP)

简介: 给定两个字符串,求解这两个字符串的最长公共子序列(Longest Common Sequence)。 比如字符串1:BDCABA;字符串2:ABCBDAB则这两个字符串的最长公共子序列长度为4,最长公共子序列是:BCBA思路: 1.

给定两个字符串,求解这两个字符串的最长公共子序列(Longest Common Sequence)。
比如字符串1:BDCABA;字符串2:ABCBDAB

则这两个字符串的最长公共子序列长度为4,最长公共子序列是:BCBA

思路: 1.分解子问题, 由空串与空串最长公共子序列的问题递推到两个字符串的最长公共子序列
2.从空串开始 保存每一个最长公共子序列,为下一个比自己大的字符串服务

递推公式:

             = 0;     当i或j = 0 空串

maxLen[i][j] = maxLen[i-1][j-1] + 1;   当sz1[i-1] == sz2[j - 1]   字符相对

             = max(maxLen[i][j-1] , 
                         maxLen[i-1][j]);   当sz1[i-1] != sz2[j - 1]   字符不相对,则为i-1或j-1中最大的

递推过程:

#include <iostream>
#include <cstring>
using namespace std;
char sz1[1000];
char sz2[1000];
int maxLen[1000][1000];
int main() {
    while (cin >> sz1 >> sz2) {
        int length1 = strlen(sz1);
        int length2 = strlen(sz2);
        int nTmp;
        int i, j;
        //初始化边界,空串为0   i=0时 或 j=0时
        for ( i = 0; i <= length1; i++) 
            maxLen[i][0] = 0;
        for ( j = 0; j <= length2; j++)
            maxLen[0][j] = 0;

        for (i = 1; i <= length1; i++) {
            for (j = 1; j <= length2; j++) {
                if (sz1[i-1] == sz2[j - 1])
                    maxLen[i][j] = maxLen[i-1][j-1] + 1;
                else
                    maxLen[i][j] = max(maxLen[i][j-1] , 
                        maxLen[i-1][j]);
                /*打印 可以看出过程
                for (int i = 1; i <= length1; i++) {
                    for (int j = 1; j <= length2; j++) {
                        cout << maxLen[i][j] << " ";    
                    }
                    cout << endl;
                }
                cout <<endl;
                */
            }
        }
        cout << maxLen[length1][length2];
    }
} //时间复杂度O(nm)2个子串长度
目录
相关文章
|
7月前
|
存储
最长公共子序列(LCS)
最长公共子序列(LCS) “【5月更文挑战第21天】”
85 2
1265:【例9.9】最长公共子序列 2021-01-15
1265:【例9.9】最长公共子序列 2021-01-15
最长公共子序列(二 | 记录路径版)
最长公共子序列(二 | 记录路径版)
最长公共子序列(二 | 记录路径版)
最长公共子序列(一 | 计算长度版)
最长公共子序列(一 | 计算长度版)
|
算法 BI
最长公共子序列(三 | 存在多个解的情况)
最长公共子序列(三 | 存在多个解的情况)
|
人工智能 Java
LCS最长公共子序列
例如 b c d d e和 a c e e d e的公共子串为c d e。 如果使用暴力,复杂度太高会直接超时。就需要使用动态规划
107 0