LCS算法詳解

一、LCS算法代碼

/**
 * 通過動態規劃的思想求出字符串 str1 和 str2 的最長公共子序列
 * 空間複雜度 O(nm)
 * 時間複雜度 O(nm)
 */
public static String getLCS(String str1, String str2) {
    int len1 = str1.length();
    int len2 = str2.length();
    int[][] dp = new int[len1][len2];

    // 初始化第一行
    for (int i = 0; i < len1; i++) {
        if (str1.charAt(i) == str2.charAt(0)) {
            dp[i][0] = 1;
        } else if (i != 0) {
            dp[i][0] = dp[i - 1][0];
        } else {
            dp[i][0] = 0;
        }
    }

    // 初始化第一列
    for (int j = 0; j < len2; j++) {
        if (str1.charAt(0) == str2.charAt(j)) {
            dp[0][j] = 1;
        } else if (j != 0) {
            dp[0][j] = dp[0][j - 1];
        } else {
            dp[0][j] = 0;
        }
    }

    // 通過動態規劃的思想，求出 dp 數組
    for (int i = 1; i < len1; i++) {
        for (int j = 1; j = 0 && j >= 0) {
        if (str1.charAt(i) == str2.charAt(j)) {
            sb.append(str1.charAt(i));
            i--;
            j--;
        } else if (i > 0 && dp[i][j] == dp[i - 1][j]) {
            i--;
        } else if (j > 0 && dp[i][j] == dp[i][j - 1]) {
            j--;
        }
    }

    return sb.reverse().toString();
}

二、LCS算法C語言

/*
 * 通過動態規劃的思想求出字符串 s1 和 s2 的最長公共子序列
 * 空間複雜度 O(nm)
 * 時間複雜度 O(nm)
 */
char* lcs(char *s1, char *s2) {
    int len1 = strlen(s1);
    int len2 = strlen(s2);
    int dp[len1][len2];

    // 初始化第一行
    for (int i = 0; i < len1; i++) {
        if (s1[i] == s2[0]) {
            dp[i][0] = 1;
        } else if (i != 0) {
            dp[i][0] = dp[i - 1][0];
        } else {
            dp[i][0] = 0;
        }
    }

    // 初始化第一列
    for (int j = 0; j < len2; j++) {
        if (s1[0] == s2[j]) {
            dp[0][j] = 1;
        } else if (j != 0) {
            dp[0][j] = dp[0][j - 1];
        } else {
            dp[0][j] = 0;
        }
    }

    // 通過動態規劃的思想，求出 dp 數組
    for (int i = 1; i < len1; i++) {
        for (int j = 1; j = 0 && j >= 0) {
        if (s1[i] == s2[j]) {
            res[dp[i][j] - 1] = s1[i];
            i--;
            j--;
        } else if (i > 0 && dp[i][j] == dp[i - 1][j]) {
            i--;
        } else if (j > 0 && dp[i][j] == dp[i][j - 1]) {
            j--;
        }
    }
    
    return res;
}

三、LCS算法公式

LCS(str1, str2) = LCS(str1-1, str2-1) + 1, if str1[m] = str2[n]

LCS(str1, str2) = max(LCS(str1-1, str2), LCS(str1, str2-1)), if str1[m] ≠ str2[n]

四、LCS算法偽代碼

算法輸入：兩個字符串 S 和 T

算法輸出：S 和 T 的最長公共子序列

dp[i][j] 表示 S[1:i] 和 T[1:j] 的最長公共子序列的長度

for i in 1 to |S|
    for j in 1 to |T|
        if S[i] == T[j]
            dp[i][j] = dp[i-1][j-1] + 1
        else
            dp[i][j] = max(dp[i-1][j], dp[i][j-1])
end for

五、LCS算法複雜度

根據偽代碼可以得出，LCS算法的時間複雜度是 O(nm)，空間複雜度也是 O(nm)。

六、LCS算法C表和B表

在 LCA 算法中，B 表就是一個記錄點和深度信息的數組。在 LCS 算法中，B 表是一個記錄選擇路徑信息的數組，用於還原 LCS。C 表是記錄動態規劃狀態的數組，用於計算 LCS 長度。

    /*  簡化版 B表 */
    for (int i = 1; i <= len1; i++) {
        for (int j = 1; j = dp[i][j - 1]) {
                dp[i][j] = dp[i - 1][j];
                b[i][j] = '↑';
            } else {
                dp[i][j] = dp[i][j - 1];
                b[i][j] = '←';
            }
        }
    }

七、LCS算法怎麼輸出

通過反向遍歷 B 表，就能找到 LCS 了。

StringBuilder sb = new StringBuilder();
int i = len1;
int j = len2;
while (i > 0 && j > 0) {
    switch (b[i][j]) {
        case '↖':
            sb.append(str1.charAt(i - 1));
            i--;
            j--;
            break;
        case '↑':
            i--;
            break;
        case '←':
            j--;
            break;
        default:
            break;
    }
}
return sb.reverse().toString();

八、LCS算法是什麼意思

LCS 的全稱是 Longest Common Subsequence，即最長公共子序列，是一種計算兩個序列之間的最長公共子序列的算法。

九、LCS排名

在字符串匹配領域，LCS 算法是一種經典的方法，被廣泛應用於文本編輯器、代碼比較工具、版本控制工具等領域。同時，LCS 算法也是一個經典的動態規劃問題，被用作編程面試及其他計算機科學領域的課程提及。