最长公共字串和最长公共子序列

最长公共字串,字符必须连续

public static int lcs(String str1,String str2){
        int len1 = str1.length();
        int len2 = str2.length();
        int c[][] = new int[len1+1][len2+1];
        int res=0;
        for (int i = 1; i <= len1; i++) {
            for( int j = 1; j <= len2; j++) {
                if (str1.charAt(i-1) == str2.charAt(j-1)) {
                    c[i][j] = c[i-1][j-1] + 1;
                    res=max(res,c[i][j]);
                } else {
                    c[i][j] = 0;
                }
            }
        }
        return res;

    }

最长公共子序列,字符不需要连续

public static int lcs(String str1,String str2){
        int len1 = str1.length();
        int len2 = str2.length();
        int c[][] = new int[len1+1][len2+1];
        for (int i = 1; i <= len1; i++) {
            for( int j = 1; j <= len2; j++) {
                if (str1.charAt(i-1) == str2.charAt(j-1)) {
                    c[i][j] = c[i-1][j-1] + 1;
         
                } else {
                    c[i][j] = max(c[i-1][j],c[i][j-1]);
                }
            }
        }
        return c[len1][len2];

    }