首页用c语言实现def lcs(a, b): m, n = len(a), len(b) c = [[0] * (n+1) for i in range(m+1)] for i in range(1, m+1): for j in range(1, n+1): if a[i-1] == b[j-1]: c[i][j] = c[i-1][j-1] + 1 else: c[i][j] = max(c[i][j-1], c[i-1][j]) res = "" i, j = m, n while i > 0 and j > 0: if a[i-1] == b[j-1]: res = a[i-1] + res i -= 1 j -= 1 elif c[i-1][j] > c[i][j-1]: i -= 1 else: j -= 1 return resa = "ABCDBAB"b = "BDCABA"print(lcs(a, b)) # output: BCBA

用c语言实现def lcs(a, b): m, n = len(a), len(b) c = [[0] * (n+1) for i in range(m+1)] for i in range(1, m+1): for j in range(1, n+1): if a[i-1] == b[j-1]: c[i][j] = c[i-1][j-1] + 1 else: c[i][j] = max(c[i][j-1], c[i-1][j]) res = "" i, j = m, n while i > 0 and j > 0: if a[i-1] == b[j-1]: res = a[i-1] + res i -= 1 j -= 1 elif c[i-1][j] > c[i][j-1]: i -= 1 else: j -= 1 return resa = "ABCDBAB"b = "BDCABA"print(lcs(a, b)) # output: BCBA

时间: 2024-01-20 19:03:59 浏览: 93

以下是使用 C 语言实现 lcs 函数的代码： ```c #include <stdio.h> #include <string.h> #define MAX_LEN 100 char* lcs(char* a, char* b) { int m = strlen(a), n = strlen(b); int c[MAX_LEN + 1][MAX_LEN + 1]; memset(c, 0, sizeof(c)); for(int i = 1; i <= m; i++) { for(int j = 1; j <= n; j++) { if(a[i-1] == b[j-1]) c[i][j] = c[i-1][j-1] + 1; else c[i][j] = (c[i-1][j] > c[i][j-1]) ? c[i-1][j] : c[i][j-1]; } } char* res = (char*)malloc(sizeof(char) * (c[m][n] + 1)); int i = m, j = n, k = c[m][n]; while(i > 0 && j > 0) { if(a[i-1] == b[j-1]) { res[--k] = a[i-1]; i--; j--; } else if(c[i-1][j] > c[i][j-1]) { i--; } else { j--; } } res[c[m][n]] = '\0'; return res; } int main() { char a[] = "ABCDBAB"; char b[] = "BDCABA"; char* res = lcs(a, b); printf("%s\n", res); free(res); return 0; } ``` 输出结果为 "BCBA"。

阅读全文