题目描述
给定两个长度分别为 N 和 M 的字符串 A 和 B,求既是 A 的子序列又是 B 的子序列的字符串长度最长是多少。
输入格式
第一行包含两个整数 N 和 M。
第二行包含一个长度为 N 的字符串,表示字符串 A。
第三行包含一个长度为 M 的字符串,表示字符串 B。
字符串均由小写字母构成。
输出格式
输出一个整数,表示最大长度。
数据范围
1≤N,M≤1000
样例
4 5
acbd
abedc
3
算法1
(动态规划) $O(n^2)$
我刚开始听的时候没理解集合,然后就一直懵逼,直到最后自己动手写的时候才理解了,在前i,前j个字母前出现的必须同时包含在两个序列中
时间复杂度
$O(n^2)$
参考文献
C++ 代码
#include <iostream>
using namespace std;
const int N = 1005;
int f[N][N];
char a[N], b[N];
int n, m;
int main()
{
scanf("%d%d", &n, &m);
scanf("%s%s", a + 1, b + 1);
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j++)
{
f[i][j] = max(f[i - 1][j], f[i][j - 1]);
if (a[i] == b[j]) f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1);
}
printf("%d\n", f[n][m]);
return 0;
}
算法2
(动态规划) $O(n^2)$
这一种是在算法设计与分析第二版王晓东著的书上学到的,其实本质都是一样的,只是代码写的略微不同,不同在利用这种可以追溯到是哪些个字母
时间复杂度
$O(n^2)$
参考文献
C++ 代码
#include <iostream>
using namespace std;
const int N = 1005;
int f[N][N];
char s1[N], s2[N];
int n, m;
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> s1[i];
for (int i = 1; i <= m; i++) cin >> s2[i];
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
{
if (s1[i] == s2[j]) f[i][j] = f[i - 1][j - 1] + 1;
else if (f[i][j - 1] >= f[i - 1][j]) f[i][j] = f[i][j - 1];
else if (f[i][j - 1] < f[i - 1][j]) f[i][j] = f[i - 1][j];
}
cout << f[n][m] << endl;
return 0;
}