求两字符串匹配的最长子序列

如果两种特征序列的公共子序列越长表示越接近，现在请你帮助计算出最长的公共特征。

输入说明：

本问题有多组测试数据，第一行就是测试数据的组数（1<=组数<=20）。对于每一组测试数据，有两行，每一行都是有大写英文字母组成的特征序列（1<=特征序列的长度<=1000）。



输出说明：

对于每一组输入，对应的输出只有一行，即最长的公共子序列的长度。

Sample Input:

1

ABDCRHGWDWSDSKJDSKDFHJKFDKJDSAFKJFDAKFDSAJFDKASDJLFLDKF

ERUDSHDFHGFLKGFGFKGFLKSAEWALUTRHGFKIFDGITRMDFLKDSLSDLLEHJFKLEKIREFMFK

Sample Output:

25


#include<iostream>
#include<string>

using namespace std;

#define MAX 1001

int nZ[MAX][MAX];

void vInit(int nA,int nB);
void vGetLcs(string sA,string sB);
int nMax(int nA,int nB);
void vOut(int nA,int nB);

int main()
{
    int i;
    int nCase;
    string sX,sY;
    int nX,nY;
    
    cin>>nCase;
    for(i=1;i<=nCase;i++)
    {
        cin>>sX>>sY;
        sX=" "+sX;
        sY=" "+sY;
        nX=sX.size()-1;
        nY=sY.size()-1;
        vInit(nX,nY);
        vGetLcs(sX,sY);
        vOut(nX,nY);
    }
    return 0;
}


void vInit(int nA,int nB)
{
    int i,j;
    
    for(j=1;j<=nB;j++)
    {
        nZ[0][j]=0;
    }

    for(i=1;i<=nA;i++)
    {
        nZ[i][0]=0;
    }
}

void vGetLcs(string sA,string sB)
{
    int i,j;
    int nA,nB;
    nA=sA.size()-1;
    nB=sB.size()-1;

    for(i=1;i<=nA;i++)
    {
        for(j=1;j<=nB;j++)
        {
            if(sA[i]==sB[j])
            {
                nZ[i][j]=nZ[i-1][j-1]+1;
            }
            else
            {
                nZ[i][j]=nMax(nZ[i][j-1],nZ[i-1][j]);
            }
        }
    } 
}

int nMax(int nA,int nB)
{
    return(nA>nB?nA:nB);
}

void vOut(int nA,int nB)
{
    cout<<nZ[nA][nB]<<endl;
}