当前位置： 移动技术网 > IT编程>开发语言>C/C++ > 最长公共子序列（DP）

最长公共子序列（DP）

2018年01月10日  | 移动技术网IT编程  | 我要评论

孝在我心中,哲理小短文,祼体艺术

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));
    }
}

 

您可能感兴趣的文章:

如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网