学步园

#include <iostream>

#include <string.h>

using namespace std;


#define NUM 100

int public_length(char *a, char *b)

{    

    int lena = strlen(a);

    int lenb = strlen(b);

    int DP[NUM][NUM];

    for(int i=0; i<=lena; i++)

        DP[i][0] = 0;

    for(int j=0; j<=lenb; j++)

        DP[0][j] = 0;

    for(int i=1; i<=lena; i++)

        for(int j=1; j<=lenb; j++)

        {

            if(a[i-1] == b[j-1])

            {

                DP[i][j] = DP[i-1][j-1] + 1;

            }

            else

            {

                if(DP[i-1][j] < DP[i][j-1])

                    DP[i][j] = DP[i][j-1];

                else

                    DP[i][j] = DP[i-1][j];

            }

        }

    return DP[lena][lenb];

}


int main()

{    

    char a[NUM];

    char b[NUM];

    int T;

    cin>>T;

    

    for(int i=0; i<T; i++)

    {

        cin>>a;

        cin>>b;

        int result = public_length(a, b);

        cout<<result<<endl;

    }

    return 0;

}