Longest Common Subsequence

最大公共子序列(LCS)

定义

LCS是Longest Common Subsequence的缩写，即最长公共子序列。一个序列，如果是两个或多个已知序列的子序列，且是所有子序列中最长的，则为最长公共子序列。

LCS不是唯一的，它可以有很多种，例如<A,B,C,B,D,A,B>和<B,D,C,A,B,A>的最长子序列可以是<B,C,A,B>也可以是<B,C,B,A>，显然都成立。

PS: LCS和LIS的原理及求解思路极其类似(因为本质上都是dp思想)，甚至有的题目会要求你求解LCIS(最长公共上升子序列)

实现方式

1.常规动态规划 O(nm)

动态规划做法，其实原理很简单，就是看当前的位上是否匹配的问题，然后根据这个来转移状态

设有长度为n的串S与长度为m的串T，用$f[i,j]$表示S串前i个字符与T串前j个字符的LCS则有:
$f[i,j]=max(f[i−1,j],f[i,j−1],(f[i−1,j−1]+1)∗[Si=Tj])$
也就是说，无论如何，一定有
$f[i,j]=max(f[i−1,j],f[i,j−1])$
讨论特殊情况:当$Si=Tj$时
$f[i,j]=max(f[i,j],f[i−1,j−1]+1)$
所以我们可以从这推出结果，然后$f[n,m]$就是最后的答案
因为$f[i]$总是会从$f[i−1]$这一维度转移过来，所以我们可以考虑用滚动数组来优化空间复杂度

int dp(string a,string b) {
    int n = a.size();
    int m = b,size();
    int now = 0;
    for (int i = 0; i <= n; i++) {
        now ^= 1;
        for (int j = 1; j <= m; j++) {
            f[now][j] = max(f[now ^ 1][j], f[now][j - 1]);
            tmp = f[now ^ 1][j - 1] + 1;
            if (a[i] == b[j] && f[now][j] < tmp)
                f[now][j] = tmp;
        }
    }
    return f[now][m]);
}

2.$O(nlogn)$的几种做法(同理于LIS)

如果我可以通过把这个原来的序列转化为另外一个序列然后求LIS来得到LCS就好了，那么怎么去转换这两个问题呢?

我们不难发现，LIS是用来求最长上升子序列的，所以当一个序列是升序排序，另外一个序列乱序时，求两个序列的LCS其实就是在求乱序序列的LIS，因为有一个序列是升序的，所以一定存在乱序序列的最长上升子序列与升序序列的序列有最长公共子序列，所以就可以求出来了

所以我们在一开始输入A序列的时候就将它序列中的元素逐一编号，然后再在B序列给对应的元素编上在A序列中的编号，也就是B序列中元素在A序列中的位置,然后去求改变后的B序列的LIS就好了。

warning

1. 在两个序列有不同元素的时候，处理的时候要去掉不同的元素，否则LISLIS可能会包含另外一个序列没有的元素而导致答案错误
2. 在两个序列中有重复的元素时，不能用该方法处理

这个应该很简单了，代码参考LIS那篇博客即可。

补充——$LCIS$实现

我们可以结合上面的LIS和LCS的思想来思考这个问题

$LIS:$

令$f[i]$表示以第i个元素结尾的LIS长度

则有: $f[i]=max(f[i],f[j]+1),(a[j]<a[i],j<i)$

$LCS:$

设有长度为n的串S与长度为m的串T，用$f[i,j]$表示S串前i个字符与T串前j个字符的LCS则有:

$f[i,j]=max(f[i−1,j],f[i,j−1],(f[i−1,j−1]+1)∗[Si=Tj])$

稍加组合思考我们可以发现:

当$f[i,j]$表示A序列前i个元素和B序列前j个元素的LCIS，t表示LCIS的结尾元素位置，则有:

$f[i,j]=f[i−1,j],Ai≠Bj$

$f[i,j]=max(f[i−1,j],f[i−1,t]+1),Ai=Bj$

又发现$f[i]$这一维每次都是从$f[i−1]$这一维转移过来，所以我们可以用滚动数组优化一下得到:

$f_i$代表序列A前i个元素与序列B的LCIS，t为结尾位置，有

$f_j=f_t+1,A_i=B_j$

在计算LCIS的长度的过程中我们可以顺便记录前驱然后输出具体的序列，所以就可以用$O(nm)$的时间复杂度算出LCIS长度与LCIS的具体序列

Code:

int n, m, Max = 0;
void output(int x) {
    if (!x)
        return;
    output(pos[x]);
    printf("%d ", b[x]);
}
int dp(int a[], int b[]) {
    for (int i = 1, t = 0; i <= n; i++, t = 0)
        for (int j = 1; j <= m; j++) {
            if (a[i] == b[j])
                f[j] = f[t] + 1, pos[j] = t;  // f[j] 的结尾
            if (a[i] > b[j] && f[t] < f[j])
                t = j;  // 保证t在结尾位置
        }
    for (int i = 1; i <= m; i++)
        if (f[i] > f[Max])
            Max = i;
    printf("%d\n", f[Max]);
    output(Max);
    return 0;
}

模板题

【模板】最长公共子序列

【模板】最长公共子序列

题目描述

给出 $1,2,\ldots,n$ 的两个排列 $P_1$ 和 $P_2$ ，求它们的最长公共子序列。

输入格式

第一行是一个数 $n$。

接下来两行，每行为 $n$ 个数，为自然数 $1,2,\ldots,n$ 的一个排列。

输出格式

一个数，即最长公共子序列的长度。

样例 #1

样例输入 #1

5 
3 2 1 4 5
1 2 3 4 5

样例输出 #1

3

提示

• 对于 $50%$ 的数据， $n \le 10^3$；
• 对于 $100%$ 的数据， $n \le 10^5$。

AC代码

#include <bits/stdc++.h>
using namespace std;
#define M 100007
#define N 1007
#define INF 0x3f3f3f3f
#define mod 99999997
#define ll long long
#define db double
#define pii pair<int, int>
int n;
int dp[M], ans[M], a[M], b[M];
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        ans[a[i]] = i;
    }
    for (int i = 1; i <= n; i++) {
        cin >> b[i];
        dp[i] = INF;
    }
    int len = 0;
    dp[0] = 0;
    for (int i = 1; i <= n; i++) {
        int l = 0, r = len, mid;
        if (ans[b[i]] > dp[len]) {
            dp[++len] = ans[b[i]];
        } else {
            while (l < r) {
                mid = (l + r) / 2;
                if (dp[mid] > ans[b[i]]) {
                    r = mid;
                } else {
                    l = mid + 1;
                }
            }
            dp[l] = min(ans[b[i]], dp[l]);
        }
    }
    cout << len;
    return 0;
}