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

Published: 19 Dec 2018 Category: algorithm

一、最长公共子序列

Longest common subsequence.

获取长度:

public int longestCommonSubsequence(String str1, String str2) {
    if (str1.isEmpty() || str2.isEmpty()) {
        return 0;
    }
    int m = str1.length();
    int n = str2.length();
    int[][] arr = new int[m + 1][n + 1];
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                arr[i][j] = arr[i - 1][j - 1] + 1;
            } else {
                arr[i][j] = Math.max(arr[i - 1][j], arr[i][j - 1]);
            }
        }
    }
    return arr[m][n];
}

获取内容

public String getLongestCommonSubsequence(String str1, String str2) {
    if (str1.isEmpty() || str2.isEmpty()) {
        return "";
    }
    int i, j;
    int m = str1.length();
    int n = str2.length();
    int[][] arr = new int[m + 1][n + 1];
    for (i = 1; i <= m; i++) {
        for (j = 1; j <= n; j++) {
            if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                arr[i][j] = arr[i - 1][j - 1] + 1;
            } else {
                arr[i][j] = Math.max(arr[i - 1][j], arr[i][j - 1]);
            }
        }
    }
    
    i = 0;
    j = 0;
    int tmp = arr[m][n];
    StringBuilder stringBuilder = new StringBuilder();
    while (tmp > 0) {
        for (; j < n; j++) {
            if (tmp > arr[m - i][n - j - 1]) {
                break;
            }
        }
        for (; i < m; i++) {
            if (tmp > arr[m - i - 1][n - j]) {
                break;
            }
        }
        stringBuilder.insert(0, str1.charAt(m - i - 1));
        tmp = arr[m - (++i)][n - (++j)];
    }
    return stringBuilder.toString();
}

二、最长公共子串

Longest common substring.

获取长度:

public int longestCommonSubstring(String str1, String str2) {
    if (str1.isEmpty() || str2.isEmpty()) {
        return 0;
    }
    int m = str1.length();
    int n = str2.length();
    int max = 0;
    int[][] arr = new int[m + 1][n + 1];
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= m; j++) {
            if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                arr[i][j] = arr[i - 1][j - 1] + 1;
                if (max < arr[i][j]) {
                    max = arr[i][j];
                }
            } else {
                arr[i][j] = 0;
            }
        }
    }
    return max;
}

获取内容:

public String getLongestCommonSubstring(String str1, String str2) {
    if (str1.isEmpty() || str2.isEmpty()) {
        return "";
    }
    int m = str1.length();
    int n = str2.length();
    int max = 0;
    int pos = 0;
    int[][] arr = new int[m + 1][n + 1];
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                arr[i][j] = arr[i - 1][j - 1] + 1;
                if (max < arr[i][j]) {
                    max = arr[i][j];
                    pos = i;
                }
            } else {
                arr[i][j] = 0;
            }
        }
    }
    return str1.substring(pos - max, pos);
}

上述两种方法,空间复杂度均为S(m*n), 时间复杂度均为O(m*n).