简答题 偏难
#7309

公共子序列 我们称序列 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;stdio.h&gt; #include &lt;string.h&gt; int max(int a, int b) {   if (a &gt; b)     return a;   else     return b; } int main() {   char s1[201], s2[201];   while (scanf("%s %s", s1, s2) != EOF) {     int dp[201][201];     memset(dp, 0, sizeof(dp));     int m = strlen(s1), n = strlen(s2);     for (int i = 1; i &lt;= m; i++) {       for (int j = 1; j &lt;= n; j++) {         if (s1[i - 1] == s2[j - 1]) {           dp[i][j] = dp[i - 1][j - 1] + 1;         } else {           dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);         }       }     }     printf("%d\n", dp[m][n]);   }   return 0; }</pre>
这道题暂未补解析。