简答题 偏难
#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 &lt;bits/stdc++.h&gt; #include &lt;string&gt; using namespace std; int f[1000][1000]; int main() {   string a, b;   while (cin &gt;&gt; a &gt;&gt; b) {     int n = a.size();     int m = b.size();     memset(f, 0, sizeof(f));     for (int i = 1; i &lt;= n; i++) {       for (int k = 1; k &lt;= 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 &lt;&lt; f[n][m] &lt;&lt; endl;   }   return 0; }</pre>
这道题暂未补解析。