最长公共子序列C语言实现

最长公共子序列（Longest Common Subsequence，LCS）是指两个字符串中最长的共同字符序列，这些字符不必连续，但顺序不变。在C语言中，我们可以使用动态规划的方法来解决这个问题。以下是一个简单的C语言函数`lcs`，用于计算两个字符串的LCS：

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

#define MAX_LENGTH 100

char lcs(char* X, char* Y, int m, int n) {
    int L[m + 1][n + 1];

    // 初始化L数组
    for (int i = 0; i <= m; i++) {
        for (int j = 0; j <= n; j++) {
            if (i == 0 || j == 0)
                L[i][j] = 0;
            else if (X[i - 1] == Y[j - 1])
                L[i][j] = L[i - 1][j - 1] + 1;
            else
                L[i][j] = max(L[i - 1][j], L[i][j - 1]);
        }
    }

    // 返回结果
    char result[MAX_LENGTH];
    int index = L[m][n];
    int i = m, j = n;

    while (i > 0 && j > 0) {
        if (X[i - 1] == Y[j - 1]) {
            result[index - 1] = X[i - 1];
            i--;
            j--;
            index--;
        } else if (L[i - 1][j] > L[i][j - 1]) {
            i--;
        } else {
            j--;
        }
    }

    result[index] = '\0'; // 添加结束符
    return result;
}

// 辅助函数用于返回两个数的最大值
int max(int a, int b) {
    return a > b ? a : b;
}

int main() {
    char str1[] = "ABCDGH";
    char str2[] = "AEDFHR";
    printf("The LCS is: %s\n", lcs(str1, str2, strlen(str1), strlen(str2)));
    return 0;
}