最长公共子序列问题

2024-03-15 13:58:23

最长公共子序列问题

问题描述：给你两个字符串$s$和$t$，找出这两个字符串的最长公共子序列

一些定义：

子序列

给定两个序列$X=<x_1,x_2,...,x_n>$和序列$Z = <z_1 , z_2 , ...,z_k>$,若存在$X$的一个严格递增下标序列$<i_1 , i_2 , ...,i_k>$，使得对所有的$j = 1 , 2 , ... , k$，有$x_{i_j} = z_j$ , 则称$Z$是$X$的子序列。也即删掉序列$X$中的零个或多个元素，而不改变元素的相对顺序所构成的新的序列就是$X$的子序列。
公共子序列

对给定的两个序列$X$和$Y$，若序列$Z$既是$X$的的子序列，也是$Y$的子序列，则称$Z$是$X$和$Y$的公共子序列。如，$X=<A,B,C,B,D,A,B>,Y=<B,D,C,A,B,A>$，则序列$<B,C,A>$是$X$和$Y$的一个公共子序列。
最长公共子序列$(LCS)$

两个序列的长度最大的公共子序列称为它们的最长公共子序列。

$LCS$问题的最优子结构性

定理$6.2$ 设有序列$X=<x_1,x_2,...,x_m>$和$Y=<y_1,y_2,...,y_n>$，并设序列$Z=<z_1,z_2,...,z_k>$为$X$和$Y$的任意一个$LCS$。

若$x_m＝y_n$，则$z_k=x_m=y_n$，且$Z_{k-1}$是$X_{m-1}$和$Y_{n-1}$的一个$LCS$。
若$x_m \neq y_n$，则$z_k\neq x_m$蕴含$Z$是$X_{m-1}$和$Y$的一个$LCS$。
若$x_m\neq y_n$，则$z_k\neq y_n$蕴含$Z$是$X$和$Y_{n-1}$的一个$LCS$。

证明：

如果$z_k\neq x_m$，则可以添加$x_m$（也即$y_n$）到$Z$中，从而可以得到$X$和$Y$的一个长度为$k+1$的公共子序列。这与$Z$是$X$和$Y$的最长公共子序列的假设相矛盾，故必有$z_k=x_m=y_n$。同时，如果$X_{m-1}$和$Y_{n-1}$有一个长度大于$k - 1$的公共子序列$W$，则将$x_m$ （也即$y_n$）添加到$W$上就会产生一个$X$和$Y$的长度大于$k$的公共子序列，与$Z$是$X$和$Y$的最长公共子序列的假设相矛盾，故$Z_{k-1}$必是$X_{m - 1}$和$Y_{n - 1}$的$LCS$。
若$z_k \neq x_m$，设$ X_{m - 1}$和$Y$有一个长度大于$k$的公共子序列$W$，则$W$也应该是$X_m$和$Y$的一个公共子序列。这与$Z$是$X$和$Y$的一个$LCS$的假设相矛盾。故$Z$是$X_{m - 1}$和$Y$的一个$LCS$。
同上

上述定义说明两个序列的一个$LCS$也包含了两个序列的前缀的$LCS$，也即$LCS$问题具有最优子结构性质。

问题一

问题二

P1439 【模板】最长公共子序列

题目描述：给出 $1,2,...,n$ 的两个排列$P_1$和$P_2$求它们的最长公共子序列。

数据范围:$ 1\leq n \leq 10^5$

思路：如果直接使用问题一种的状态转移方程，则复杂度为$O(n^2)$，显然不可接受。考虑到此题的两个序列是两个排列，也即序列中的元素各不相同，我们令$A = P_1$ ， $B= P_2$如果我们定义映射关系$g(B_i) = i$，然后再让$A_i = g(A_i)$ ，那么$B$序列就变成了$1 , 2 , ..., n$ ，而$A$就是$1 , 2 , ... , n$的一个排列。此时要求这两个序列的最长公共子序列等价于求解序列$A$的一个最长上升子序列$LIS$。事实上，只要$A,B$两个序列中有一个的元素是各不相同的就可以使用这种方法对原问题进行转化然后求解。

时间复杂度：$O(nlogn)$

参考代码：

#include<bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;

int a[N], b[N], c[N];
int n;
int LIS() {
	int len = 1;
	c[len] = b[1];
	for (int i = 2; i <= n; ++i) {
		if (b[i] > c[len]) c[++len] = b[i];
		else {
			int l = 1, r = len, pos = 0;
			while (l <= r) {
				int mid = l + r >> 1;
				if (c[mid] < b[i]) pos = mid, l = mid + 1;
				else r = mid - 1;
			}
			c[pos + 1] = b[i];
		}
	}
	return len;
}
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
	for (int i = 1; i <= n; ++i) scanf("%d", &b[i]);
	for (int i = 1; i <= n; ++i) c[a[i]] = i, a[i] = i;
	for (int i = 1; i <= n; ++i) b[i] = c[b[i]];
	printf("%d\n", LIS());
	return 0;
}

问题三

P2758 编辑距离

72. 编辑距离

题目描述：设$A$和$B$是两个字符串。我们要用最少的字符操作次数，将字符串$A$转换为字符串$B$。这里所说的字符操作共有三种：1. 插入一个字符;2.删除一个字符;3.替换一个字符。（均为小写字母。）

思路：定义状态$f_{i , j}$表示串$A$长度为$i$的前缀与串$B$长度为$j$的前缀的编辑距离。当$A_i = B_j$时，$f_{i , j} = f_{i - 1 , j - 1}$，否则，有以下三种方案：

在串$A$长度为$i - 1$的前缀和串$B$长度为$j - 1$的前缀匹配的情况下使用一次修改操作
在串$A$长度为$i - 1$的前缀和串$B$长度为$j$的前缀匹配的情况下使用一次删除操作
在串$A$长度为$i$的前缀和串$B$长度为$j - 1$的前缀匹配的情况下使用一次添加操作

故其转移方程为：

\[f_{i , j} = \begin{cases} 0 & i = 0 , j = 0\\ f_{i - 1 , j - 1} & A_i = B_j\\ min\{f_{i - 1 , j - 1} , f_{i - 1 , j} , f_{i , j - 1}\} + 1 & A_i \neq B_j \end{cases} \]

时间复杂度:$O(|A| \times |B|)$
参考代码：

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 1; i <= (n); ++i)
#define rrep(i, n) for (int i = 0; i <= (n); ++i)
using std::cin;
using std::cout;
using std::string;
using std::vector;
using std::min;

int main() {
	string A, B;
	cin >> A >> B;
	
	int n = A.size(), m = B.size();
	A = ' ' + A, B = ' ' + B;
	vector<vector<int>> f(n + 1, vector<int>(m + 1, 1e8));
	
	rrep(i, n) f[i][0] = i;
	rrep(i, m) f[0][i] = i;
	
	rep(i, n)rep(j, m) {
		f[i][j] = min(f[i - 1][j], f[i][j - 1]) + 1;
		int t = A[i] != B[j];
		f[i][j] = min(f[i][j], f[i - 1][j - 1] + t);
	}
	
	cout << f[n][m] << '\n';
	
	return 0;
}

码农公寓

最长公共子序列问题