DDOSvoid's Blog

最长公共子序列

发表于 更新于 分类于
本文字数： 1.1k 阅读时长 ≈ 1 分钟

简介

LCS

算法

首先我们看一下最简单且使用的 $O(n^2)$ 做法

我们令 f[i][j] 表示第一个序列匹配到第i个，第二个序列匹配到第j个时的最长公共子序列的长度

转移直接继承或者是i和j匹配

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <cstdio>
#define maxn 1010
using namespace std;

int n, a[maxn], b[maxn];

int f[maxn][maxn]; 

int main() {
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1; i <= n; ++i) cin >> b[i];
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j) {
            f[i][j] = max(f[i - 1][j], f[i][j - 1]); 
            if (a[i] == b[j]) f[i][j] = f[i - 1][j - 1] + 1;
        }
    cout << f[n][n] << endl; 
    return 0;
}

另外我们考虑如何处理序列中没有相同元素的特殊情况，能否将时间复杂度优化到 $O(n^2)$ 以下

我们考虑在原方法当且仅当a[i]==b[j]时才会增加f的值

所以我们考虑在这方面进行优化

我们对第二个数组做一个类似hash的东西

我们将每个数变成在第一个数组中出现该数的下标

那么问题被转换成了LIS问题

时间复杂度 $O(nlogn)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <cstdio>
#include <algorithm>
#define maxn 100010
using namespace std;

int n, a[maxn], b[maxn], p[maxn]; 

int d[maxn], len;

int main() {
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i], p[a[i]] = i;
    for (int i = 1; i <= n; ++i) cin >> b[i], b[i] = p[b[i]]; 
    for (int i = 1; i <= n; ++i) {
        if (b[i] > d[len]) d[++len] = b[i];
        else *lower_bound(d + 1, d + len + 1, b[i]) = b[i]; 
    } cout << len << endl; 
    return 0;
}