最长公共子序列（LCS）详解

最长公共子序列（Longest Common Subsequence）解法和优化

谈完LIS，下面来谈一谈LCS（最长公共子序列问题），本文主要分析一下该问题的一般解法和较优解法，基本上基于两道题目：一般的LCS问题 和 洛谷P1439。

一般的LCS问题解法

问题描述

给定两个字符串$s_1s_2…s_n$和$t_1t_2…t_m$。求出这两个字符串中最长的公共子序列的长度。

数据范围：$1\leq n,m\leq1000$

Sample Input:
1
2
3 5 
ade abcde
Sample Output:
1
3

一般解法

这是一道很经典的动态规划入门题，具体思路：

定义状态：$dp[i][j]$表示字符串$s_1s_2…s_i$和$t_1t_2…t_j$的LCS长度
状态转移：我们发现，以上状态可以通过如下几种状态转移得到：

当$s_{i+1}=t_{j+1}$时，表明两个序列这一项出现了公共成分，那么就应该在$s1s_2…s_i$和$t_1t_2…t_j$的LCS结尾追加上$s{i+1}$，即$dp[i+1][j+1]=dp[i][j]+1$；

除上述情况之外的其他情况，都不能再原先LCS上追加，那么新状态就应该等于某一个旧状态，应当是是$dp[i+1][j]$和$dp[i][j+1]$两者中的较大者。

至此，所有状态都考虑完毕了，状态转移方程可以写成如下形式：

$dp[i+1][j+1]=\begin{cases}dp[i][j]+1\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (s_{i+1}=t_{j+1}) \\ \max(dp[i+1][j],dp[i][j+1])\ \ \ \ (else) \end{cases}$

AC代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int const maxn = 10005;
ll dp[maxn][maxn];
char a[maxn],b[maxn];
int main(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=1;i<=m;i++){
		cin>>b[i];
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(a[i]==b[j]){
				dp[i][j] = dp[i-1][j-1]+1;
			}else{
				dp[i][j] = max(dp[i-1][j],dp[i][j-1]); 
			}
		}
	}
	cout<<dp[n][m];
	return 0;
}

可以看出，上述解法的时间复杂度为$O(nm)$，对于本题数据完全可以AC，但对于较大的数据量就必然会暴毙，因此下面介绍一种更优($O(nlogn)$)的解法。

洛谷P1439 [模板]最长公共子序列

当然，这道题出现在了$nlogn$数据结构的模板题里面，明摆着是要我们优化时间复杂度吧。。下面看题：

问题描述

给出1~n的两个全排列，求它们的LCS

数据规模：$n\leq1e5$

Sample Input:
1
2
3
5 
3 2 1 4 5
1 2 3 4 5
Sample Output:
1
3

单纯的我照着一般解法搞了一下这题，混了50分。。。
毫无追求的我

哦豁，数据量这么大，连dp数组都开不了，更别说双重循环的复杂度了，这可咋办呢？
~~我也是有追求的~~

$nlogn$解法

莫慌，这题明摆着需要logn的方法，那么我们想想，最简单的logn方法是什么呢？

对了，就是二分！

那么，想要二分，就必须要找到单调有序的东西，这道题看起来好像找不到单调有序的东西啊。。。

我们回想一下之前学过的LIS，对了，LIS的nlogn解法不就是利用的状态数组的单调性吗？那么这道LCS的题可不可以也用LIS的方法来解呢？

我们发现，与LIS不同的是，本体有两个数组需要考虑，求其公共，而LIS只有一个数组，求其最长上升，最长上升，最简单的上升是什么？1234567对不对？再仔细琢磨，难道不可以把求LIS想象成是求原数组和1234567…这样一个有序数组的LCS吗？

这么一想，这题似乎有着落了，但还剩下一个问题，就是题目的两个数组都是乱的，这该怎么办呢？

那还不简单，随便挑一个数组把他“编码成”（或者说“看成”，行话叫哈希表或者map或者离散化）类似于1234567的单调上升数组不就行了，然后再依照这个编码去找和另一个数组的LCS，于是这题就被完美地解决了。

附上AC代码（其中的二分可以去看LIS的那篇文章作了解，这里不加赘述）

AC代码

#include<bits/stdc++.h>
using namespace std;
int n;
int a[100005],b[100005],f[100005];
int fun[100005],len;

int bound(int x){
	int l=1,r=len;
	while(l<r){
		int mid = (l+r)>>1;
		if(f[mid]>x){
			r = mid;
		}else l = mid +1;
	}
	return l;
}

int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		fun[a[i]]=i;
	}
	for(int i=1;i<=n;i++){
		cin>>b[i];
	}
	for(int i=1;i<=n;i++){
		if(f[len]<fun[b[i]]){
			f[++len] = fun[b[i]];
		}else{
			int pos = bound(fun[b[i]]);
			f[pos] = fun[b[i]];
		}
	}
	cout<<len<<endl;
	return 0;
}

完美！

可以看出，本题有两个关键点：
1. 找出映射关系，即编码一个数组为单调上升的；
2. 利用LIS的二分思想，即要知道f数组是单调上升的，这里只是换了个形式。
  以上。

那么，咱来搞一道题？

洛谷P2782 友好城市

题目链接

解法

~~这难道不是裸的上一题吗？~~

在草稿纸上胡乱画一通，发现先把南北友好城市都绑定在一起，因为城市是按照坐标排的，于是我随便找一边sort一下，看对应的另一边，有如下规律：

如果一边是 2 4，另一边对应着 6 2，那么这个航道就必相交，因为正常排的时候会把另一边也排好顺序，如果是上述这种情况，在另一边排好序的情况下是一定会有相交出现的。所以可以简单地推出如下规律：
这个时候，另一边的最长上升子序列（LIS）就是答案呀！

才发现这个题和上面的模板题如出一辙，这个还要简单一些，因为不需要自己编码，排个序就相当于完成了编码工作。

废话少说

AC代码

#include<bits/stdc++.h>
using namespace std;
int n,fun[200005];
int f[200005],len;
struct node{
	int a,b;
}p[200005];

bool cmp(node x1,node x2){
	return x1.a<x2.a;
}
int bound(int x){
	int l=1,r=len;
	while(l<r){
		int mid = (l+r)>>1;
		if(f[mid]>x) r = mid;
		else l = mid + 1;
	}
	return l;
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>p[i].a>>p[i].b;
	}
	sort(p+1,p+n+1,cmp);
	for(int i=1;i<=n;i++){
		if(p[i].b>f[len]){
			f[++len] = p[i].b;
		}else{
			int pos = bound(p[i].b);
			f[pos] = p[i].b;
		}
	}
	cout<<len<<endl;
	return 0;
}

算法

刷题动态规划二分

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议，转载请注明出处！

划分数的问题上一篇

最长上升子序列（LIS）详解下一篇