两个字符串的最长公共子序列长度_求2个字符串的最长公共子序列和最长公共子字符串的c语言代码

好的，下面是求解最长公共子序列和最长公共子字符串的C语言代码：

求解最长公共子序列

int longest_common_subsequence(char* s1, char* s2) {
int m = strlen(s1), n = strlen(s2);
int dp[m+1][n+1];
memset(dp, 0, sizeof(dp));
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (s1[i-1] == s2[j-1]) {
dp[i][j] = dp[i-1][j-1] + 1;
} else {
dp[i][j] = fmax(dp[i-1][j], dp[i][j-1]);
}
}
}
return dp[m][n];
}
登录后复制

求解最长公共子字符串

char* longest_common_substring(char* s1, char* s2) {
int m = strlen(s1), n = strlen(s2);
int dp[m+1][n+1];
memset(dp, 0, sizeof(dp));
int max_len = 0;
int end_pos = 0;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (s1[i-1] == s2[j-1]) {
dp[i][j] = dp[i-1][j-1] + 1;
if (dp[i][j] > max_len) {
max_len = dp[i][j];
end_pos = i;
}
} else {
dp[i][j] = 0;
}
}
}
char* res = (char*)malloc(sizeof(char) * (max_len + 1));
strncpy(res, s1 + end_pos - max_len, max_len);
res[max_len] = '\0';
return res;
}
登录后复制
这两段代码同样使用动态规划的思想来解决最长公共子序列和最长公共子字符串问题。其中，dp[i][j] 表示第一个字符串的前 i 个字符和第二个字符串的前 j 个字符之间的最长公共子序列（或子字符串）长度。最终的最长公共子序列（或子字符串）长度为 dp[m][n]，其中 m 和 n 分别为两个字符串的长度。通过倒推 dp 数组，我们可以得到最长公共子序列（或子字符串）具体是哪些字符。注意，在C语言中需要手动分配和释放内存。