题目链接
description
给出两个字符串a b，求a与b的最长公共子序列（子序列不要求是连续的）。
比如两个串为：
abcicba
abdkscab
ab是两个串的子序列，abc也是，abca也是，其中abca是这两个字符串最长的子序列。
input
第1行：字符串a
第2行：字符串b
(a,b的长度 <= 1000)
output
输出最长的子序列，如果有多个，随意输出1个。
input示例
abcicba
abdkscab
output示例
abca
代码如下：
#include <iostream> #include <algorithm> #include <cstring> #include <cstdio> #include <cmath> using namespace std; const int n = 1005; int dp[n][n]; char s1[n], s2[n], s[n]; void getlca(int i,int j,int k) { if (k<0) return; if (s1[i]==s2[j]) { s[k] = s2[j]; //or s[k]=s1[i]. getlca(i-1,j-1,k-1); return; } if (dp[i - 1][j] >= dp[i][j - 1]) getlca(i-1,j,k); else getlca(i, j - 1, k); } int main() { while (scanf("%s", s1) != eof) { scanf("%s", s2); int len_s1 = strlen(s1); int len_s2 = strlen(s2); memset(dp,0,sizeof(dp)); for (int i = 0; i < len_s1; i++) { for (int j = 0; j < len_s2; j++) { if (i == 0 || j == 0) { dp[i][j] = (s1[i] == s2[j]); if (i) dp[i][j] = max(dp[i][j], dp[i - 1][j]); if (j) dp[i][j] = max(dp[i][j], dp[i][j - 1]); continue; } dp[i][j] = max(dp[i][j-1], dp[i - 1][j]); dp[i][j] = max(dp[i][j],dp[i-1][j-1]+(s1[i]==s2[j])); } } int len = dp[len_s1 - 1][len_s2 - 1]; s[len] = ' '; getlca(len_s1-1,len_s2-1,len-1); puts(s); } }
本文来自网络收集，不代表计算机技术网立场，如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址：https://www.ctvol.com/c-cdevelopment/607398.html