求最长公共子序列c语言代码

求最长公共子序列 (Longest Common Subsequence, LCS) 的 C 语言代码通常会用到动态规划的方法。下面是一个简单的版本，用于找出两个字符串的最长公共子序列：

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

// 动态规划函数，lcs[i][j] 存储 s1 和 s2 的前 i 个字符和前 j 个字符的最长公共子序列长度
int lcs(char* s1, char* s2, int m, int n) {
    int dp[m + 1][n + 1];
    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 (s1[i - 1] == s2[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];
}

// 辅助函数，返回两数中的较大值
int max(int a, int b) {
    return a > b ? a : b;
}

int main() {
    char str1[50], str2[50];
    printf("请输入第一个字符串: ");
    fgets(str1, sizeof(str1), stdin);
    str1[strlen(str1) - 1] = '\0'; // 去掉换行符

    printf("请输入第二个字符串: ");
    fgets(str2, sizeof(str2), stdin);
    str2[strlen(str2) - 1] = '\0';

    int len = lcs(str1, str2, strlen(str1), strlen(str2));
    printf("最长公共子序列的长度是: %d\n", len);

    return 0;
}