Cyborg Genes UVA - 10723

该题目是LCS的变形，对于输入的两个字符串，想得到以两个字符串为字串的字符串的长度，那么也就是两个字符串的长度之和减去这两个字符串的最长的公共子串的长度，所以可以很容易的求出长度。

同时，假设两个字符串为a和b，利用数组s[i][j]记录以a[0...i]以及b[0...j]为子串的最短字符串的数量，如果在a的位置i的字符a[i]和b的位置j的字符b[j]是相等的，那么s[i][j]=s[i-1][j-1]，因为这个时候等于是在已知最短串的末尾加上相应的相等的字符即可，也就相当于最短串的数量还是不变的；如果出现a[i]!=b[j]，如果f[i-1][j]>f[i][j-1]，那么f[i][j]=f[i-1][j],

s[i][j]=s[i-1][j]，因为选取的公共子串的长度是a[0...i-1]以及b[0...j]的最长子串的长度，那么对应的以a[0...i]以及b[0...j]为子串的串数量也就是以a[0...i-1]以及b[0...j]为子串的串数量，同理可以处理f[i-1][j]<f[i][j-1]的情况。当f[i-1][j]==f[i][j-1]的时候，说明可以选取s[i-1][j]以及s[i][j-1]两种情况，所以对应的串的数量为两者的数量之和，具体实现见如下代码：

package a;//实际提交的时候记得去掉包名

import java.util.Arrays;
import java.util.Scanner;

public class Main {

    int T;
    String s1,s2;
    long s[][]=new long[32][32];//s代表的是数量
    long f[][]=new long[32][32];//f代表的是长度

    public void Solve(){
        Scanner scan=new Scanner(System.in);
        T=scan.nextInt();
        scan.nextLine();//去掉回车
        int Case=0;
        while(T>0){
            T--;
            s1=scan.nextLine();
            s2=scan.nextLine();
            int L1=s1.length();
            int L2=s2.length();
            for(int i=0;i<=L1;i++){
                for(int j=0;j<=L2;j++){
                    s[i][j]=0;
                    f[i][j]=0;
                }
            }
            for(int i=0;i<=L1;i++)
                s[i][0]=1;
            for(int j=0;j<=L2;j++)
                s[0][j]=1;
            for(int i=1;i<=L1;i++){
                for(int j=1;j<=L2;j++){
                    if(s1.charAt(i-1)==s2.charAt(j-1)){
                        f[i][j]=f[i-1][j-1]+1;
                        s[i][j]=s[i-1][j-1];
                    }
                    else if(f[i-1][j]>f[i][j-1]){
                        f[i][j]=f[i-1][j];
                        s[i][j]=s[i-1][j];
                    }
                    else if(f[i-1][j]<f[i][j-1]){
                        f[i][j]=f[i][j-1];
                        s[i][j]=s[i][j-1];
                    }
                    else{
                        f[i][j]=f[i][j-1];
                        s[i][j]=s[i-1][j]+s[i][j-1];
                    }
                }
            }
            Case++;
            System.out.printf("Case #%d: %-1d %-1d\n",Case,L1+L2-f[L1][L2],s[L1][L2]);
        }
    }

    public static void main(String[] args){
        Main a=new Main();
        a.Solve();
    }

}