最长公共子串

思路
最长公共子串是两个字符串最长相同的连续子序列；最长公共子序列是两个字符串最长相同的可非连续子序列，思路可以和最长公共子序列一样(动态规划经典例题——最长公共子序列和最长公共子串 )，但是仅仅用二维数组只能得到递推关系，即当前最优解为上一个解+1：dp[i][j]=dp[i-1][j-1],无法确定连续的子串，故需要定义一个 maxLength记录最长公共子串的最大长度，还需定义一个end记录当前字符串的下标值，这样最长连续子串就可以通过str2.substring(end-maxLength+1,end+1)得到。
代码：

public String LCS (String str1, String str2) {

    // write code here

    int[][] nums = new int[str1.length()+1][str2.length()+1];
    if(str1 == null || str2 == null || str1.equals("") || str2.equals("")){
        return "-1";
    }
    int maxLength = 0;   //记录最长公共子串长度
    int end =0;          //记录最长子串最后一个字符的下标
    int m=str1.length();
    int n=str2.length();

    //初始化表格边界
    for(int i = 0; i <= m; ++i) nums[i][0] = 0;
    for(int j = 0; j <= n; ++j) nums[0][j] = 0;

    //循环"填表"
    for (int i=1;i<=m;i++){
        for (int j=1;j<=n;j++){
            if (str1.charAt(i-1)==str2.charAt(j-1)){
                nums[i][j]=nums[i-1][j-1]+1;
            }else {
                nums[i][j]=0;
            }
            //记录最长子串的长度和当前下标
            if (nums[i][j]>=maxLength){
                maxLength=nums[i][j];
                end=j-1;
            }
        }
    }
    //如果没有公共子串
    if (maxLength==0){
        return "-1";
    }else {
        String result = str2.substring(end-maxLength+1,end+1);
        return result;
    }
}