最长公共子序列(DP)
2018-06-18 03:55:16来源:未知 阅读 ()
一个给定序列的子序列是在该序列中删去若干元素后得到的序列。确切地说,若给定序列 X = { x1,x2,…,xm },则另一序列Z ={ z1,z2,…,zk },X 的子序列是指存在一个严格递增下标序列{ i1,i2,…,ik },使得对于所有 j = 1,2,…,k ,有 zj = xij
给出两个字符序列 X 和 Y ,求出它们的最长公共子序列。
输入的第一行为测试样例的个数T,接下来有T个测试样例。每个测试样例的第一行是字符串 X ,第二行是字符串 Y。X 和 Y 只包含大写字母,且长度不大于1000。
对应每个测试样例输出一行,只有一个整数,表示字符串 X 和字符串 Y 的最长公共子序列的长度。
2
ABCDE
ACE
AAABBBCCC
AABBCC
3
6
#include<iostream> #include<stdio.h> #include<string.h> using namespace std; char x[1001]; char y[1002]; int c[1001][1001]; void length(int x_len,int y_len){ for(int i=1;i<=x_len;i++){ for(int j=1;j<=y_len;j++){ if(x[i-1]==y[j-1]){ c[i][j]=c[i-1][j-1]+1; }else c[i][j]=max(c[i-1][j],c[i][j-1]); } } cout << c[x_len][y_len] << endl; } int main(){ int T; cin >> T; for(int i=1;i<=T;i++){ scanf("%s%s",x,y); length(strlen(x),strlen(y)); } }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:数据结构--链表
下一篇:通过被调函数改变主调函数的值
- 最长回文子串 2020-04-13
- 无重复字符的最长子串 2020-04-08
- 整数去重 2020-02-23
- 算法训练 拦截导弹(最长递增子序列和最长递减子序列问题, 2020-02-20
- 序列归并 2020-02-19
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