题目描述
给定两个长度分别为N和M的字符串A和B,求既是A的子序列又是B的子序列的字符串长度最长是多少。
输入格式
第一行包含两个整数N和M。
第二行包含一个长度为N的字符串,表示字符串A。
第三行包含一个长度为M的字符串,表示字符串B。
字符串均由小写字母构成。
输出格式
输出一个整数,表示最大长度。
数据范围
1≤N,M≤1000
样例
输入:
4 5
acbd
abedc
输出:
3
解题思路
DP
公共子序列不一定连续。例如,第一个字符串是acbd,第二个字符串是abedc,则他们的最大公共子序列为“abd”,所以最大公共子序列长度为3 。
闫氏DP分析法
状态表示:
集合:
所有A[1 ~ i]与B[1 ~ j]的公共子序列的集合
属性:
MAX(长度最大值)
状态计算:
划分子集,找最后一个不同点,即A的最后一个字符A[i]是否包含在该公共子序列中,以及B的最后一个字符B[j]是否包含在该公共子序列中。由此我们可知,A[i]、B[j]都分别有两种选择,我们可以用“0”来表示不包含,“1”来表示包含,我们用“00”表示都不包含,“01”表示只包含B[j],用“10”表示只包含A[i],用“11”表示A[i]、B[j]都包含。
- 我们考虑“11”这种情况,由于A[i]和B[j]都分别是A、B的最后一个字符,若要同时包含A[i]和B[j],必须满足A[i]和B[j]相等,否则不存在。若A[i]和B[j]相等的情况存在,则这个集合的每一个公共子序列在A中一定是A[x], A[x], …… , A[i];在B中一定是B[x], B[x], …… , B[j]。我们可以将这两个公共子序列分为两部分,一部分是未知的前i个A中的公共子序列部分和前j个B中的公共子序列部分,另一部分是固定不变的A[i]和B[j],所以它的长度最大值为f[i - 1, j - 1] + 1。
- 我们考虑“00”这种情况,由于A[1 ~ i], B[1 ~ j]的最长公共子序列中A[i]和B[j]存在,即A[1 ~ i - 1], B[1 ~ j - 1]的最长公共子序列,所以它的长度最大值为f[i - 1, j - 1]。
- 我们考虑“01”这种情况(不包含A[i],含有B[j]),因为f[i - 1, j]表示A[1 ~ i - 1]与B[1 ~ j]中选的所有公共子序列,所以A[i]是一定不包含的,但是不一定包含B[j]。所以f[i - 1, j]分子序列中B[j]存在和B[j]不存在两种情况,因为是求最大值所以有重复部分也不妨碍最终的结果,所以它的长度最大值为f[i - 1, j]。
- “10”情况同理,它的长度最大值为f[i, j - 1]。
另外,我们可以看出f[i - 1, j - 1]这种方案是包含于f[i - 1, j]中的,所以直接考虑后三种方案即可。
注意:求数量时要保证不重不漏,求最大值的时候重复是无所谓的。
图例
算法
C++ 代码
#include <iostream>
using namespace std;
const int N = 1010;
int n, m;
char a[N], b[N];
int f[N][N];
int main()
{
cin >> n >> m;
cin >> a + 1 >> b + 1; //让a,b从下标1开始输入
for(int i = 1 ; i <= n ; i++){
for(int j = 1 ; j <= m ; j++){
if(a[i] == b[j])
f[i][j] = max(f[i][j] , f[i - 1][j - 1] + 1);
else
f[i][j] = max(f[i - 1][j] , f[i][j - 1]);
}
}
cout << f[n][m] << endl;
return 0;
}