最长公共子序列（lcs）代码实现

c语言实现带回溯的lcs

1. 我们将 lcs 函数分成两个部分：一个部分计算长度，另一个部分构造LCS字符串。
2. 我们需要先计算LCS长度，然后分配适当大小的内存，再构造LCS字符串。

完整的C代码：

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

// LCS算法实现并返回LCS长度
int lcs_length(const char *X, const char *Y) {
    int m = strlen(X);
    int n = strlen(Y);
    int **dp = (int **)malloc((m + 1) * sizeof(int *));
    for (int i = 0; i <= m; i++) {
        dp[i] = (int *)malloc((n + 1) * sizeof(int));
    }

    // 填充dp数组
    for (int i = 0; i <= m; i++) {
        for (int j = 0; j <= n; j++) {
            if (i == 0 || j == 0) {
                dp[i][j] = 0;
            } else if (X[i - 1] == Y[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = dp[i - 1][j] > dp[i][j - 1] ? dp[i - 1][j] : dp[i][j - 1];
            }
        }
    }

    int result = dp[m][n];

    // 释放dp数组
    for (int i = 0; i <= m; i++) {
        free(dp[i]);
    }
    free(dp);

    return result;
}

// 构造LCS字符串
void construct_lcs(const char *X, const char *Y, char *lcs_str) {
    int m = strlen(X);
    int n = strlen(Y);
    int **dp = (int **)malloc((m + 1) * sizeof(int *));
    for (int i = 0; i <= m; i++) {
        dp[i] = (int *)malloc((n + 1) * sizeof(int));
    }

    // 填充dp数组
    for (int i = 0; i <= m; i++) {
        for (int j = 0; j <= n; j++) {
            if (i == 0 || j == 0) {
                dp[i][j] = 0;
            } else if (X[i - 1] == Y[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = dp[i - 1][j] > dp[i][j - 1] ? dp[i - 1][j] : dp[i][j - 1];
            }
        }
    }

    int index = dp[m][n];
    lcs_str[index] = '\0';  // 设置字符串结束符

    int i = m, j = n;
    while (i > 0 && j > 0) {
        if (X[i - 1] == Y[j - 1]) {
            lcs_str[index - 1] = X[i - 1];
            i--;
            j--;
            index--;
        } else if (dp[i - 1][j] > dp[i][j - 1]) {
            i--;
        } else {
            j--;
        }
    }

    // 释放dp数组
    for (int i = 0; i <= m; i++) {
        free(dp[i]);
    }
    free(dp);
}

// 主函数
int main() {
    char X[] = "ABCBDAB";
    char Y[] = "BDCAB";
    int lcs_len = lcs_length(X, Y);  // 获取LCS长度

    char *lcs_str = (char *)malloc((lcs_len + 1) * sizeof(char));
    construct_lcs(X, Y, lcs_str);  // 构造LCS字符串

    printf("最长公共子序列的长度: %d\n", lcs_len);
    printf("最长公共子序列: %s\n", lcs_str);

    free(lcs_str);

    return 0;
}

解释

1. 计算LCS长度的函数 lcs_length：

   • 这个函数计算并返回LCS的长度。它使用动态分配的二维数组 dp 来存储中间结果，最终返回 dp[m][n]。

2. 构造LCS字符串的函数 construct_lcs：

   • 这个函数使用与 lcs_length 相同的方法填充 dp 数组，然后通过回溯 dp 数组来构造LCS字符串。

3. 主函数 main：

   • 首先调用 lcs_length 计算LCS长度。
   • 然后分配足够的内存来存储LCS字符串，并调用 construct_lcs 来构造LCS字符串。
   • 最后，打印LCS长度和LCS字符串，并释放分配的内存。

编译和运行

输出应该是：

最长公共子序列的长度: 4
最长公共子序列: BDAB

这个输出表示字符串 “ABCBDAB” 和 “BDCAB” 的最长公共子序列的长度为4，并且最长公共子序列为 “BDAB”。

C++实现

#include <iostream>
#include <vector>
#include <string>

using namespace std;

// LCS算法实现并返回LCS长度
int lcs_length(const string &X, const string &Y) {
    int m = X.length();
    int n = Y.length();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

    // 填充dp数组
    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (X[i - 1] == Y[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[m][n];
}

// 构造LCS字符串
string construct_lcs(const string &X, const string &Y) {
    int m = X.length();
    int n = Y.length();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

    // 填充dp数组
    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (X[i - 1] == Y[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }

    // 构造LCS字符串
    int i = m, j = n;
    string lcs_str;
    while (i > 0 && j > 0) {
        if (X[i - 1] == Y[j - 1]) {
            lcs_str.push_back(X[i - 1]);
            --i;
            --j;
        } else if (dp[i - 1][j] > dp[i][j - 1]) {
            --i;
        } else {
            --j;
        }
    }
    reverse(lcs_str.begin(), lcs_str.end());
    return lcs_str;
}

// 主函数
int main() {
    string X = "ABCBDAB";
    string Y = "BDCAB";

    int lcs_len = lcs_length(X, Y);
    string lcs_str = construct_lcs(X, Y);

    cout << "最长公共子序列的长度: " << lcs_len << endl;
    cout << "最长公共子序列: " << lcs_str << endl;

    return 0;
}

Python实现

def lcs_length(X, Y):
    m = len(X)
    n = len(Y)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if X[i - 1] == Y[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

    return dp[m][n]

def construct_lcs(X, Y):
    m = len(X)
    n = len(Y)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if X[i - 1] == Y[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

    lcs_str = []
    i, j = m, n
    while i > 0 and j > 0:
        if X[i - 1] == Y[j - 1]:
            lcs_str.append(X[i - 1])
            i -= 1
            j -= 1
        elif dp[i - 1][j] > dp[i][j - 1]:
            i -= 1
        else:
            j -= 1

    lcs_str.reverse()
    return ''.join(lcs_str)

# 示例用法
X = "ABCBDAB"
Y = "BDCAB"

lcs_len = lcs_length(X, Y)
lcs_str = construct_lcs(X, Y)

print(f"最长公共子序列的长度: {lcs_len}")
print(f"最长公共子序列: {lcs_str}")

解释

1. 计算LCS长度的函数：

   • C++的 lcs_length 和Python的 lcs_length 函数使用动态分配的二维数组 dp 来存储中间结果，最终返回 dp[m][n]。

2. 构造LCS字符串的函数：

   • C++的 construct_lcs 和Python的 construct_lcs 函数使用与 lcs_length 相同的方法填充 dp 数组，然后通过回溯 dp 数组来构造LCS字符串。

3. 主函数：

   • C++和Python的主函数分别调用 lcs_length 计算LCS长度，然后调用 construct_lcs 构造LCS字符串，最后打印LCS长度和LCS字符串。