用c语言实现最长公共子序列

最长公共子序列（Longest Common Subsequence）是指两个序列中都存在的最长的子序列。子序列是指不改变字符在序列中的相对顺序，通过删除一些字符后得到的新序列。

以下是用动态规划算法实现的最长公共子序列的C语言代码：

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

#define MAXLEN 100

int LCS(char* str1, char* str2, int m, int n, int dp[][MAXLEN]) {
    int i, j;
    for (i = 0; i <= m; i++) {
        for (j = 0; j <= n; j++) {
            if (i == 0 || j == 0) {
                dp[i][j] = 0;
            } else if (str1[i-1] == str2[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];
            }
        }
    }
    return dp[m][n];
}

int main() {
    char str1[MAXLEN], str2[MAXLEN];
    int dp[MAXLEN][MAXLEN];
    int m, n;

    printf("Enter the first string: ");
    scanf("%s", str1);
    printf("Enter the second string: ");
    scanf("%s", str2);

    m = strlen(str1);
    n = strlen(str2);

    printf("The length of the longest common subsequence is: %d\n", LCS(str1, str2, m, n, dp));

    return 0;
}

这段代码中，LCS() 函数实现了动态规划算法。它接受两个字符串 str1 和 str2，以及它们的长度 m 和 n，以及一个二维数组 dp。dp[i][j] 存储的是 str1 的前 i 个字符和 str2 的前 j 个字符的最长公共子序列的长度。

LCS() 函数首先将 dp 数组的第一行和第一列初始化为 0。然后，它遍历整个二维数组，计算 dp[i][j]。如果 str1[i-1] 等于 str2[j-1]，那么 dp[i][j] 就等于 dp[i-1][j-1] + 1，因为 str1 的前 i-1 个字符和 str2 的前 j-1 个字符的最长公共子序列加上 str1[i-1]（或 str2[j-1]）就是 str1 的前 i 个字符和 str2 的前 j 个字符的最长公共子序列。如果 str1[i-1] 不等于 str2[j-1]，那么 dp[i][j] 就等于 dp[i-1][j] 和 dp[i][j-1] 中的最大值，因为不管 str1[i-1] 和 str2[j-1] 是否相等，它们都不能属于最长公共子序列的最后一个字符，所以 dp[i][j] 就是不包括它们的最长公共子序列的长度。

最后，main() 函数读入两个字符串，调用 LCS() 函数计算它们的最长公共子序列的长度，并输出结果。