For given two sequences X and Y, a sequence Z is a common subsequence of X and Y if Z is a subsequence of both X and Y. For example, if X={a,b,c,b,d,a,b} and Y={b,d,c,a,b,a}, the sequence {b,c,a}is a common subsequence of both X and Y. On the other hand, the sequence {b,c,a} is not a longest common subsequence (LCS) of X and Y, since it has length 3 and the sequence {b,c,b,a}, which is also common to both X and Y, has length 4. The sequence {b,c,b,a} is an LCS of X and Y, since there is no common subsequence of length 5 or greater.
Write a program which finds the length of LCS of given two sequences X and Y. The sequence consists of alphabetical characters.
The input consists of multiple datasets. In the first line, an integer q which is the number of datasets is given. In the following 2×q lines, each dataset which consists of the two sequences X and Y are given.
For each dataset, print the length of LCS of X and Y in a line.
3
abcbdab
bdcaba
abc
abc
abc
bc
4
3
2
用X(i)、Y(j)来代替X、Y中的每一个元素。那么,求长度为m,n的序列的最长公共子序列(LCS),的问题,我们可以把它转化为局部问题来求解。
1、当x(m) = y(n) 时,那么Xm与Yn的LCS就是LCS(X(m-1)、Y(n-1))+1
2、当X(m)≠Y(n)时,那么Xm、Yn的LCS就是max(LCS(X(m-1),Y(n)), LCS(X(m),Y(n-1))
3、当i=0或者j=0时,LCS[i][j]=0
那么我们就得出了状态转移方程了,下面就根据上面的状态转移方程敲代码就好了。
用数组dp[i][j]存储序列Xi,Yj的LCS的长度,那么我们只需要从小到大去算就可以了。
代码如下:
#include<iostream>
#include<string.h>
#include<cstdlib>
#include<cstring>
using namespace std;
int L[1005][1005] = { 0 };
int lcs(string& x, int lx, string& y, int ly)
{
if (lx == 0 || ly == 0) return 0;
if (L[lx][ly] != 0) return L[lx][ly];
if (x[lx-1] == y[ly-1])
{
L[lx][ly] = lcs(x, lx - 1, y, ly - 1) + 1;
return L[lx][ly];
}
if (x[lx-1] != y[ly-1])
{
L[lx][ly] = max(lcs(x, lx, y, ly - 1), lcs(x, lx - 1, y, ly));
return L[lx][ly];
}
}
int main()
{
int n;
cin >> n;
string x = " ", y = " ";
for (int i = 0; i < n; i++)
{
cin >> x >> y;
memset(L, 0, sizeof(int) * 1005*1005);
cout << lcs(x, x.length(), y, y.length()) << endl;
}
}