求两个字符串最长公共字符串的长度

问题描述
给出两个字符串，求出两个字符串公共字符串的最大长度
例如："acbbsdef","acbesdsd"
最大公共字符串长度为3；为acb

解题思路
采用一个二维矩阵来记录中间的结果。比如"abab"和"aba",如果两个字符相等，那么此处值等于其左上角元素加1，入下结果可知，最长的长度为3，最长的结果就是其对角线上的元素aba

/**
 * 求两个字符串的最长公共子串
 * 矩阵法
 */
public class CommonStringPro {
    /**
     * 求公共子串
     * @param str1
     * @param str2
     */
    public  static  int  getCommonStr(String str1,String str2){
        //将两个字符串转换成char数组 便于操作
        char chars1[] =str1.toCharArray();
        char chars2 []=str2.toCharArray();

        //构建二维数组 存储两个字符串相同的元素
        int res[][]=new int [chars1.length][chars2.length];

        //动态规划解决问题 把矩阵两个字符串相同的元素置为左上角元素值加1
        for (int i=0;i<chars1.length;i++){
            for (int j=0;j<chars2.length;j++){
                if (chars1[i]==chars2[j]){
                    //第一行的情况 第一列的情况
                    if (i==0||j==0){
                        res[i][j]=1;
                    }else {
                        res[i][j]=res[i-1][j-1]+1;
                    }
                }else {
                    //对于其他不相同的元素  表中设为0
                    res[i][j]=0;
                }
            }
        }

        //得到最长字符串长度
        int x=0;  int y=0;//记录最大元素下标值

        int max=0;
        for (int i=0;i<chars1.length;i++){
            for (int j=0;j<chars2.length;j++) {
                if (res[i][j]>max){
                    max=res[i][j];

                }
            }
        }
            return max;
    }

    public static void main(String[] args) {
        System.out.println(getCommonStr("acbbsdef","acbesdsd"));

        //输出结果为3
    }

}