c 最长公共子序列(lcs)
时间: 2023-12-18 09:27:10 浏览: 30
最长公共子序列(LCS)问题是指在两个字符串中找到最长的公共子序列,这里的子序列可以是不连续的一串字符。在比较两个字符串的时候,我们可以使用动态规划的方法来解决。具体来说,我们可以定义一个二维数组c,其中c[i][j]表示第一个字符串的前i个字符和第二个字符串的前j个字符的最长公共子序列的长度。然后,我们可以使用以下递归式来计算c[i][j]的值:
如果i=0或j=0,则c[i][j]=0;
如果第一个字符串的第i个字符和第二个字符串的第j个字符相等,则c[i][j]=c[i-1][j-1]+1;
如果第一个字符串的第i个字符和第二个字符串的第j个字符不相等,则c[i][j]=max(c[i-1][j],c[i][j-1])。
最终,c[m][n]就是两个字符串的最长公共子序列的长度,其中m和n分别是两个字符串的长度。如果我们需要找到最长公共子序列本身,我们可以使用类似于构建c数组的方法来构建一个记录最长公共子序列的二维数组b,其中b[i][j]表示c[i][j]是由哪个子问题的解转移而来。然后,我们可以使用以下方法来构建最长公共子序列:
从b[m][n]开始,如果b[i][j]表示c[i][j]是由c[i-1][j-1]+1转移而来,则将第一个字符串的第i个字符添加到最长公共子序列中,并将i和j分别减1;
如果b[i][j]表示c[i][j]是由c[i-1][j]转移而来,则将i减1;
如果b[i][j]表示c[i][j]是由c[i][j-1]转移而来,则将j减1。
相关问题
C语言最长公共子序列
下面是C语言实现最长公共子序列的代码和注释:
```c
#include <stdio.h>
#include <string.h>
// 定义最大字符串长度
#define MAX_LEN 100
// 定义求最长公共子序列的函数
int lcs(char *str1, char *str2) {
// 获取两个字符串的长度
int len1 = strlen(str1);
int len2 = strlen(str2);
// 定义二维数组存储最长公共子序列的长度
int dp[MAX_LEN + 1][MAX_LEN + 1];
// 初始化数组
for (int i = 0; i <= len1; i++) {
for (int j = 0; j <= len2; j++) {
dp[i][j] = 0;
}
}
// 动态规划求解最长公共子序列的长度
for (int i = 1; i <= len1; i++) {
for (int j = 1; j <= len2; j++) {
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[len1][len2];
}
int main() {
// 定义两个字符串
char str1[MAX_LEN + 1] = "zxyxyz";
char str2[MAX_LEN + 1] = "xyyzx";
// 调用lcs函数求解最长公共子序列的长度
int len = lcs(str1, str2);
// 输出结果
printf("The length of the longest common subsequence is: %d\n", len);
return 0;
}
```
c语言最长公共子序列
C语言最长公共子序列是指在两个字符串中找到最长的公共子序列的长度,其中公共子序列是指两个或多个序列中以相同顺序出现的字符序列。这个问题可以使用动态规划算法来解决,具体步骤如下:
1. 定义一个二维数组L,其中L[i][j]表示第一个字符串的前i个字符和第二个字符串的前j个字符的最长公共子序列的长度。
2. 初始化L[j]和L[i]为0,因为一个空字符串和任何字符串的最长公共子序列的长度都为0。
3. 对于i>0和j>0,如果第一个字符串的第i个字符和第二个字符串的第j个字符相同,则L[i][j] = L[i-1][j-1] + 1,否则L[i][j] = max(L[i-1][j], L[i][j-1])。
4. 最终L[n][m]就是两个字符串的最长公共子序列的长度。
下面是C语言的代码实现:
```c
#include <stdio.h>
#include <string.h>
int max(int a, int b) {
return a > b ? a : b;
}
int lcs(char *str1, char *str2, int len1, int len2) {
int L[len1+1][len2+1];
int i, j;
for (i = 0; i <= len1; i++) {
for (j = 0; j <= len2; j++) {
if (i == 0 || j == 0) {
L[i][j] = 0;
} else if (str1[i-1] == str2[j-1]) {
L[i][j] = L[i-1][j-1] + 1;
} else {
L[i][j] = max(L[i-1][j], L[i][j-1]);
}
}
}
return L[len1][len2];
}
int main() {
char str1[] = "AGGTAB";
char str2[] = "GXTXAYB";
int len1 = strlen(str1);
int len2 = strlen(str2);
printf("Length of LCS is %d\n", lcs(str1, str2, len1, len2));
return 0;
}
```