最长公共子串

//子串必须是连续的，dp[i][j]表示以str1中下标i，str2中下标j结尾的最长公共子串长度。保存长度和下标，即可求出最长子串
//而求最长公共子序列的时候，不一定连续，dp[i][j]表示str1中前i个字符与str2中前j个字符的最长公共子序列长度。
//如何得到最长公共子序列 可从后往前推 可能有多个最长公共子序列
dp[i][j]表示字符串s1的前i个字符和s2的前j个字符的最长公共子序列的长度
dp[i][j] = Math.max(dp[i-1][j-1]+1(if arr[i]==arr[j]),dp[i-1][j],dp[i][j-1])
可另外设置一个数组int[][] flag dp[i][j]=dp[i-1][j-1]+1的时候 此时flag[i][j]=1; 当dp[i][j]=dp[i-1][j] 此时flag[i][j]=2; 当dp[i][j]=dp[i][j-1] flag[i][j]=3;
通过dp的值为1 2 3倒推 即可得到具体的最长公共子序列

public static String LCS (String str1, String str2) {
        if(str1==null || str2==null) return "-1";
        // write code here
        int len1=str1.length();
        int len2=str2.length();
        int[][] dp=new int[len1][len2];
        int res = -1;
        int end=0;
        for(int i=0;i<len1;i++){
            for(int j=0;j<len2;j++){
                dp[i][j]=-1;
                if(str1.charAt(i)==str2.charAt(j)){
                    if(i==0 || j==0) dp[i][j]=1;
                    else if(dp[i-1][j-1]!=-1)
                        dp[i][j]=dp[i-1][j-1]+1;
                    else dp[i][j]=1;
                }
                if(dp[i][j]>res){
                    res=dp[i][j];
                    //System.out.println(j);
                    end=i;
                }
            }
        }
        //在没有公共子串的时候
        if(res==-1) return "-1";
        //System.out.println(res);
        return str1.substring(end-res+1,end+1);
    }