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 < len2; j++) {
            if (str1.charAt(i) == str2.charAt(j)) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }

    // 反向遍历 dp 数组，构造出最长公共子序列
    StringBuilder sb = new StringBuilder();
    int i = len1 - 1;
    int j = len2 - 1;
    while (i >= 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 < len2; j++) {
            if (s1[i] == s2[j]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    
    // 反向遍历 dp 数组，构造出最长公共子序列
    char* res = (char*) malloc(sizeof(char) * (dp[len1 - 1][len2 - 1] + 1));
    res[dp[len1 - 1][len2 - 1]] = '\0';
    int i = len1 - 1, j = len2 - 1;
    while (i >= 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 <= len2; j++) {
            if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
                b[i][j] = '↖';
            } else if (dp[i - 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 算法也是一个经典的动态规划问题，被用作编程面试及其他计算机科学领域的课程提及。