问题

计算两个字符串x和y的最长公共字串（Longest Common Substring）

说明

假设字符串x和字符串y的长度分别为m和n，用数组c的元素c[i][j]记录x中的前i个字符和y中的前j个字符的最长公共字串的长度。
c[i][j]满足最优子结构，其递归定义为：

代码

• x/y：长度分别为m/n的字符串。
• c[i][j]：记录x中前i个字符和y中的前j个字符的最长公共子序列。
• max：x/y的最长公共字串的长度。
• maxx/maxy：分别代表x/y两个字符串的公共字串的最后一个字符在xy两个字符串中的位置。

/**
 * ClassName: MaxCommonSubstr 
 * @Description:求最长的公共子序列 
 * @date 2016年5月18日
 */
public class MaxCommonSubstr {
    private String x;
    private String y;
    private int[][] maxHis;
    private int max;
    private int maxx;
    private int maxy;
    private String subStr;
    
    public MaxCommonSubstr(String x, String y) {
        this.x = x;
        this.y = y;
        maxHis = new int[x.length()][y.length()];
    }
    public void calSubstr() {
        if(x.equals("") || y.equals("")){
            max = 0;
            maxx = 0;
            maxy = 0;
            return;
        }
        for(int i = 0; i<x.length(); i++){
            String tempX = x.substring(i,i+1);
            for(int j=0; j<y.length(); j++){
                String tempY = y.substring(j,j+1);
                if(tempX.equals(tempY)){
                    if(i==0 || j==0){
                        maxHis[i][j] = 1;
                    }else{
                        maxHis[i][j] = maxHis[i-1][j-1] + 1;
                    }                   
                    if(max<maxHis[i][j]){
                        max = maxHis[i][j];
                        maxx = i;
                        maxy = j;
                    }
                }else{
                    maxHis[i][j] = 0;
                }
            }
        }
        subStr = x.substring(maxx-max+1, maxx+1);
    }
    public String getSubStr() {
        return subStr;
    }
    public static void main(String[] args) {
        String x = "abc";
        String y = "cba";
        MaxCommonSubstr mcs = new MaxCommonSubstr(x, y);
        mcs.calSubstr();
        System.out.println(mcs.getSubStr());
    }
}