【动态规划】最长公共子序列

Longest Common Subsequence

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.

Input

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.

Output

For each dataset, print the length of LCS of X and Y in a line.

Constraints

• 1≤q≤150
• 1≤length of X and Y ≤1,000
• q≤20 if the dataset includes a sequence whose length is more than 100

Sample Input 1

代码语言：javascript复制

3
abcbdab
bdcaba
abc
abc
abc
bc

Sample Output 1

代码语言：javascript复制

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的长度，那么我们只需要从小到大去算就可以了。

代码如下：

代码语言：javascript复制

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

}

dataset input output sample sequence

0 人点赞