简答题
偏难
#7200
公共子序列 我们称序列Z = < z 1 , z 2 , ..., z k >是序列X = < x 1 , x 2 , ..., x m >的子序列当且仅当存在…
公共子序列
我们称序列Z = < z1, z2, ..., zk >是序列X = < x1, x2, ..., xm >的子序列当且仅当存在 严格上升 的序列< i1, i2, ..., ik >,使得对j = 1, 2, ... ,k, 有xij = zj。比如Z = < a, b, f, c > 是X = < a, b, c, f, b, c >的子序列。 现在给出两个序列X和Y,你的任务是找到X和Y的最大公共子序列,也就是说要找到一个最长的序列Z,使得Z既是X的子序列也是Y的子序列。
时间限制:3000
内存限制:65536
输入
输入包括多组测试数据。每组数据包括一行,给出两个长度不超过200的字符串,表示两个序列。两个字符串之间由若干个空格隔开。
输出
对每组输入数据,输出一行,给出两个序列的最大公共子序列的长度。
样例输入
abcfbc abfcab programming contest abcd mnp
样例输出
4 2 0
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include <bits/stdc++.h>
#include <string>
using namespace std;
int f[1000][1000];
int main() {
string a, b;
while (cin >> a >> b) {
int n = a.size();
int m = b.size();
memset(f, 0, sizeof(f));
for (int i = 1; i <= n; i++) {
for (int k = 1; k <= m; k++) {
if (a[i - 1] == b[k - 1]) {
f[i][k] = max(f[i][k], f[i - 1][k - 1] + 1);
} else {
f[i][k] = max(f[i][k - 1], f[i - 1][k]);
}
}
}
cout << f[n][m] << endl;
}
return 0;
}</pre>
这道题暂未补解析。