首页 › 题库 › C/C++编程考级 › C/C++编程四级 › 简答题
简答题 偏难
#7487

公共子序列(2023.12) 我们称序列 Z = < z 1 , z 2 , ..., z k >是序列 X = < x 1 , x 2 , ..., x m…

公共子序列(2023.12)

我们称序列 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">// C++参考代码1 #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><pre class="brush:cpp;toolbar:false">// C++参考代码2 #include &lt;iostream&gt; #include &lt;vector&gt; #include &lt;algorithm&gt; using namespace std; int longestCommonSubsequence(string X, string Y) {     int m = X.length();     int n = Y.length();     vector&lt;vector&lt;int&gt;&gt; dp(m + 1, vector&lt;int&gt;(n + 1, 0));     for (int i = 1; i &lt;= m; i++) {         for (int j = 1; j &lt;= n; j++) {             if (X[i - 1] == Y[j - 1]) {                 dp[i][j] = dp[i - 1][j - 1] + 1;             } else {                 dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);             }         }     }     return dp[m][n]; } int main() {     string X, Y;     while (cin &gt;&gt; X &gt;&gt; Y) {         int result = longestCommonSubsequence(X, Y);         cout &lt;&lt; result &lt;&lt; endl;     }     return 0; }</pre><pre class="brush:cpp;toolbar:false">// C语言参考代码 #include &lt;stdio.h&gt; #include &lt;string.h&gt; int max(int a, int b) {     return (a &gt; b) ? a : b; } int longestCommonSubsequence(char* X, char* Y) {     int m = strlen(X);     int n = strlen(Y);     int L[m+1][n+1];     for (int i = 0; i &lt;= m; i++) {         for (int j = 0; j &lt;= n; j++) {             if (i == 0 || j == 0)                 L[i][j] = 0;             else if (X[i-1] == Y[j-1])                 L[i][j] = L[i-1][j-1] + 1;             else                 L[i][j] = max(L[i-1][j], L[i][j-1]);         }     }     return L[m][n]; } int main() {     char X[201], Y[201];     while (scanf("%s %s", X, Y) != EOF) {         int result = longestCommonSubsequence(X, Y);         printf("%d\n", result);     }     return 0; }</pre>
这道题暂未补解析。