算法设计例题:最长公共子序列(DP)
memory limit: 65536KB time limit: 500MS
accept: 50 submit: 124
Description
一个给定序列的子序列是在该序列中删去若干元素后得到的序列。确切地说,若给定序列 X = { x1,x2,…,xm },则另一序列Z={
z1,z2,…,zk },X的子序列是指存在一个严格递增下标序列{ i1,i2,…,ik },使得对于所有 j
= 1,2,…,k
,有 zj = xij
给出两个字符序列X和Y,求出它们的最长公共子序列。
Input
输入的第一行为测试样例的个数T( T < 40 ),接下来有T个测试样例。每个测试样例的第一行是字符串X,第二行是字符串Y。X和Y只包含大写字母,且长度不大于1000。
Output
对应每个测试样例输出一行,只有一个整数,表示字符串X和字符串Y的最长公共子序列的长度。
Sample Input
2
ABCDE
ACE
AAABBBCCC
AABBCC
Sample Output
3
6
Author
Eapink & CYL
解决方法:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
|
#include<iostream> #include<string.h> #define int
int
int
int
{ return
} int
{ int
char
scanf ( "%d" ,&textNum); for (k=0;k<textNum;k++) {
|