uva 10723 uva 10723 Cyborg Genes求s1,s2的最短合串即合串的组成方法数

已知两个母串s1,s2,求它们最短合串的长及组成该长度合串的方法数，用LCS解

dp[i][j]存s1[i]与s2[j]最短的合串长度，初始化dp[i][0]=dp[0][i]=i

1、当s1[i]==s2[j]时，dp[i][j]=dp[i-1][j-1]；

2、否则dp[i][j]=min(dp[i-1][j],dp[i][j-1])。

f[i][j]存s1[i]与s2[j]组成最短串的方法，初始f[i][0]=f[0][i]=1，

1、若s1[i]==s2[j]则只能放在最后，f[i][j]=f[i-1][j-1]；

2、若不相等，此时新增的s1[i],s2[j]的摆放有两种情况，一种是s1[i]放在s2[j]的后面(f[i-1][j])，另一种是s1[i]放在s2[j]的前面(f[i][j-1])，即新增的最后一个字符的前面是s1[i]还是s2[j]，这时应考虑哪种摆法是最小长度的放法，我们发现如果s2[j]参与公共子串则只能s1[i]摆在最后，同样如果s1[i]参与公共子串则只能s2[j]放在最后，而s1[i]与s2[j]是否参与了公共子串可以从dp[i][j-1]与dp[i-1][j]反映出来，若s1[i]参与了公共子串，而s2[j]没有，则dp[i][j-1] < dp[i-1][j]，这时s1[i]不用再放，只把s2[j]放到最后，f[i][j]=f[i][j-1]

#include<stdio.h>
#include<string.h>
char s1[50],s2[50];
int  dp[50][50],f[50][50];
int l1,l2;
int min(int a,int b)
{
    return a>b?b:a;
}
int main()
{
    int i,j,k,l,m,n;
    scanf("%d",&l);
    for(k=1;k<=l;k++)
    {
        scanf("%s%s",s1+1,s2+1);
        l1=strlen(s1+1);
        l2=strlen(s2+1);
        for(i=0;i<50;i++)
        {
            dp[0][i]=dp[i][0]=i;//最短合串
            f[0][i]=f[i][0]=1;  //组成最短合串的方法数
        }
        for(i=1;i<=l1;i++)
        {
            for(j=1;j<=l2;j++)
            {
                if(s1[i]==s2[j])
                {
                    dp[i][j]=dp[i-1][j-1]+1;
                    f[i][j]=f[i-1][j-1];
                }
                else
                {
                    dp[i][j]=min(dp[i-1][j],dp[i][j-1])+1;
                    if(dp[i-1][j]==dp[i][j-1])
                        f[i][j]=f[i-1][j]+f[i][j-1];
                    else if(dp[i-1][j]<dp[i][j-1])
                        f[i][j]=f[i-1][j];
                    else
                        f[i][j]=f[i][j-1];
                }
            }
        }
        printf("Case #%d: %d %d\n",k,dp[l1][l2],f[l1][l2]);
    }
    return 0;
}