本文共 1913 字，大约阅读时间需要 6 分钟。

For given two sequences XX and YY , a sequence ZZ is a common subsequence of XX and YY if ZZ is a subsequence of both XX and YY . For example, if X={a,b,c,b,d,a,b}X={a,b,c,b,d,a,b} and Y={b,d,c,a,b,a}Y={b,d,c,a,b,a} , the sequence {b,c,a}{b,c,a} is a common subsequence of both XX and YY . On the other hand, the sequence {b,c,a}{b,c,a} is not a longest common subsequence (LCS) of XX and YY , since it has length 3 and the sequence {b,c,b,a}{b,c,b,a} , which is also common to both XX and YY , has length 4. The sequence {b,c,b,a}{b,c,b,a} is an LCS of XX and YY , since there is no common subsequence of length 5 or greater.

Write a program which finds the length of LCS of given two sequences XX and YY . The sequence consists of alphabetical characters.

Input

The input consists of multiple datasets. In the first line, an integer qq which is the number of datasets is given. In the following 2×q2×q lines, each dataset which consists of the two sequences XX and YY are given.

Output

For each dataset, print the length of LCS of XX and YY in a line.

Constraints

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

Sample Input 1

3abcbdabbdcabaabcabcabcbc

Sample Output 1

432

Reference

Introduction to Algorithms, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. The MIT Press.

求最长公共子序列。 。 。

设有两个子串X，Y。 。。开一个数组dp[i][j],表示i行j列的最长公共子序列。

当i=0||j=0,dp[i][j]=0;

当xi= yj时，dp[i][j]=dp[i-1][j-1]+1;

当xi!=yj时,  dp[i][j]=max(dp[i][j-1],dp[i-1][j]) ;

代码如下:

#include 
   
    #include 
    
     #include 
     
      #include 
      
       using namespace std;const int maxn=1005;int q;char a[maxn],b[maxn];int dp[maxn][maxn];void init(){    memset (dp,0,sizeof(dp));}int main(){    scanf("%d",&q);    while (q--)    {        init();        scanf("%s\n%s",a,b);        int len1=strlen(a),len2=strlen(b);        for (int i=0;i
      
     
    
   

转载地址：http://ntaen.baihongyu.com/