lightoj1013

CODE

#include <iostream>
#include <cstring>

using namespace std;

int nCase;
int len1,len2;
char s1[35],s2[35];
int lcs[35][35];
long long dp[80][35][35];
int main()
{
        int t;
        cin >>t;
        while(t--)
        {
                memset(dp,0,sizeof(dp));
                cin >> s1+1>>s2+1 ;
                len1=strlen(s1+1),len2=strlen(s2+1);
                for(int i=1;i<=len1;i++)
                        for(int j=1;j<=len2;j++)
                {
                        if(s1[i]==s2[j])lcs[i][j]=lcs[i-1][j-1]+1;
                        else lcs[i][j]=max(lcs[i-1][j],lcs[i][j-1]);
                }
                int len=len1+len2-lcs[len1][len2];
                for(int i=0;i<=max(len1,len2);i++)
                {
                        dp[i][0][i]=1;
                        dp[i][i][0]=1;
                }
                for(int i=1;i<=len;i++)
                        for(int j=1;j<=len1;j++)
                                for(int k=1;k<=len2;k++)
                {
                        if(s1[j]==s2[k])
                        {
                                dp[i][j][k]=dp[i-1][j-1][k-1];
                        }
                        else
                        {
                                dp[i][j][k]=dp[i-1][j][k-1]+dp[i-1][j-1][k];
                        }


                }
                cout << "Case "<<++nCase<<": "<<len<<' '<<dp[len][len1][len2]<<endl;
        }
        return 0;
}