题意：给出两个串a，b，去构建另一个串，新构建出来的串要满足两个性质。一，在这个新的串中选出一个子集是a串，另外选出一个子串是b，满足这个条件后，要求这个串的长度最短。也可以这样说，ab两个串合并为一个新串，不改变a，b串本身的相对位置，但是要求新串长度最短。输出这样的新串的个数
所以基本上可以想到，是和LCS有关的，再细想，那就是算出LCS的长度，然后ab两串长度之和减去LCS的长度，相当于ab两串合并为一串，消去他们的共有元素，那么新串中还是包含了a，b串的所有元素还是可以选出一部分子集来得到a或b串的。
但问题时，怎么构建，另外有多少种构建方法，实际上构建的方案数就是最后新串的个数
我们可以模仿LCS的构建方法来思考这个问题 c[i][j]表示a串前i个元素和b串前j个元素所能得到的方案数。l[i][j]表示LCS的长度
若a[i]=b[j]，那么c[i][j]=c[i-1][j-1],即a串前i-1个元素和b串前j-1个元素得到的组合串的末尾加上一个相同的元素a[i]，那么得到的新的组合串的个数还是和之前的组合串的个数一样
若a[i]!=b[j], l[i][j]=max { l[i-1][j] , l[i][j-1]}
若l[i-1][j]>l[i][j-1],那说明从l[i-1][j]这种状态开始构建才能得到最终的LCS同时最终的组合串才不能漏掉共有的元素，所以c[i][i]=c[i-1][j],即在a串i-1个元素和b串j个元素组成的组合串的后面加上a[i]，那么得到的新的组合串的个数和之前的组合串的个数是相同的
若l[i][j-1]>l[i-1][j],道理和上面是一样的，所以c[i][j]=c[i][j-1],相当于在之前的组合串后面加上元素b[j],得到新的组合串的个数不变
若l[i][j-1]=l[i-1][j],说明从两种状态都是能得到最终的LCS并且最终的组合串不会漏掉任何相同的公共元素，所以c[i][j]=c[i-1][j]+c[i][j-1] , 即用a串的i-1个元素和b串的j个元素组成的组合串的最后加上a[i]得到新的组合串和之前的组合串个数相同，另外用a串的i个元素和b串的的j-1个元素组成的组合串的最后加上b[j]得到新的组合串和之前的组合串个数相同，那么就是两者之和
#include<bits/stdc++.h>
using namespace std;
int T;char s1[40],s2[40];int len1,len2;
int dp[40][40];
long long c[40][40];
int main(void)
{
scanf("%d",&T);getchar();
for(int i=1;i<=T;i++)
{
gets(s1+1);gets(s2+1);
memset(dp,0,sizeof(dp));
memset(c,0,sizeof(c));
len1 = strlen(s1+1),len2 = strlen(s2+1);
//注意c数组的边界条件（从0开始..）
for(int i=0;i<=len1;i++)c[i][0]=1;
for(int i=0;i<=len2;i++)c[0][i]=1;
for(int i=1;i<=len1;i++)
{
for(int j=1;j<=len2;j++)
{
if(s1[i]==s2[j])
{
dp[i][j] = dp[i-1][j-1]+1;
c[i][j] = c[i-1][j-1];
}
else
{
if(dp[i-1][j]>dp[i][j-1])
{
dp[i][j] = dp[i-1][j];
c[i][j] = c[i-1][j];
}
else if(dp[i][j-1]>dp[i-1][j])
{
dp[i][j] = dp[i][j-1];
c[i][j] = c[i][j-1];
}
else
{
dp[i][j] = dp[i-1][j];
c[i][j] = c[i-1][j]+c[i][j-1];
}
}
}
}
printf("Case #%d: %d %lld\n",i,len1+len2-dp[len1][len2],c[len1][len2]);
}
return 0;
}