E2 最长公共子序列 • EH's Blog

题目情境#

题目描述

给出一个长度为 $n(n\le 5000)$ 的字符串序列。请输出这个序列的最长公共子序列及其长度。

输入格式

输入两个字符串（代码里忽略了这个）。

输出格式

输出分为两行，

第一行输出一个整数表示最长公共子序列的长度，

第二行输出这个最长公共子序列。

算法解析：#

最长公共子序列： $f[i][j]$ 表示 $a$ 前 $i$ 个字符与 $b$ 前 $j$ 个字符的 LCS 长度。若 $a[i]==b[j]$ ， $f[i][j]=f[i-1][j-1]+1$ ；否则 $f[i][j]=\max(f[i-1][j],f[i][j-1])$ 。用 $p$ 数组记录转移方向，回溯即可还原出最长公共子序列。复杂度 $O(n^2)$ 。

p数组记录转移方向，用来还原子序列。

Python代码实现#

a = "ADABBC"
b = "DBPCA"
f = []
p = []
m = 0
n = 0

def LCS():
    global m, n, f, p
    m = len(a)
    n = len(b)
    f = [[0] * (n + 1) for _ in range(m + 1)]
    p = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if a[i-1] == b[j-1]:
                f[i][j] = f[i-1][j-1] + 1
                p[i][j] = 1  # 左上方
            else:
                if f[i][j-1] > f[i-1][j]:
                    f[i][j] = f[i][j-1]
                    p[i][j] = 2  # 左边
                else:
                    f[i][j] = f[i-1][j]
                    p[i][j] = 3  # 上边
    print(f[m][n])

def getLCS():
    global m, n, p, a
    i = m
    j = n
    k = f[m][n]
    s = [''] * k
    while i > 0 and j > 0:
        if p[i][j] == 1:
            s[k-1] = a[i-1]
            i -= 1
            j -= 1
            k -= 1
        elif p[i][j] == 2:
            j -= 1
        else:
            i -= 1
    print(''.join(s))

if __name__ == "__main__":
    LCS()
    getLCS()

python

C++代码实现#

#include <cstring>
#include <iostream>

char a[200] = "ADABBC";
char b[200] = "DBPCA";
int f[200][200];
int p[200][200];
int m, n;
void LCS() {
    int i, j;
    m = strlen(a);
    n = strlen(b);
    for (i = 1; i <= m; i++) {
        for (j = 1; j <= n; j++) {
            if (a[i-1] == b[j-1]) {
                f[i][j] = f[i-1][j-1] + 1;
                p[i][j] = 1; // 左上方
            } else if (f[i][j-1] > f[i-1][j]) {
                f[i][j] = f[i][j-1];
                p[i][j] = 2; // 左边
            } else {
                f[i][j] = f[i-1][j];
                p[i][j] = 3; // 上边
            }
        }
    }
    cout << f[m][n] << '\n';
}

void getLCS() {
    int i, j, k;
    char s[200];
    i = m;
    j = n;
    k = f[m][n];
    while (i > 0 && j > 0) {
        if (p[i][j] == 1) {
            s[k-1] = a[i-1];
            i--;
            j--;
            k--;
        } else if (p[i][j] == 2) {
            j--;
        } else {
            i--;
        }
    }
    for (i = 0; i < f[m][n]; i++) {
        cout << s[i];
    }
}
int main() {
    LCS();
    getLCS();
    return 0;
}