Description
一个给定序列的子序列是在该序列中删去若干元素后得到的序列。确切地说，若给定序列 X = { x1，x2，…，xm }，则另一序列Z ={ z1，z2，…，zk }，X 的子序列是指存在一个严格递增下标序列{ i1，i2，…，ik }，使得对于所有 j = 1，2，…，k ，有 zj = xij
给出两个字符序列 X 和 Y ，求出它们的最长公共子序列。
Input
输入的第一行为测试样例的个数T，接下来有T个测试样例。每个测试样例的第一行是字符串 X ，第二行是字符串 Y。X 和 Y 只包含大写字母，且长度不大于1000。
Output
对应每个测试样例输出一行，只有一个整数，表示字符串 X 和字符串 Y 的最长公共子序列的长度。
Sample Input
2
ABCDE
ACE
AAABBBCCC
AABBCC
Sample Output
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)); } }
内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
