51Nod-1006 最长公共子序列Lcs
2018-10-03 17:57:02来源:博客园 阅读 ()
题目链接
Description
给出两个字符串A B,求A与B的最长公共子序列(子序列不要求是连续的)。
第1行:字符串A
第2行:字符串B
(A,B的长度 <= 1000)Output
输出最长的子序列,如果有多个,随意输出1个。
Input示例
abcicba
abdkscab
Output示例
#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] = '\0'; getLCA(len_s1-1,len_s2-1,len-1); puts(s); } }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 最长回文子串 2020-04-13
- 无重复字符的最长子串 2020-04-08
- 算法训练 拦截导弹(最长递增子序列和最长递减子序列问题, 2020-02-20
- 树结构基础 2020-02-18
- 浅谈LCA 2019-12-25
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash