C++最长公共子序列
时间: 2023-11-14 22:59:52 浏览: 37
最长公共子序列是指在两个字符串中找到一个最长的序列,使得该序列在两个字符串中的字符顺序保持一致。比如对于字符串"abcfbc"和"abfcab",它们的最长公共子序列是"abcb"。
C语言可以用动态规划来解决最长公共子序列问题。动态规划的思路是,定义一个二维数组dp,其中dp[i][j]表示字符串1的前i个字符和字符串2的前j个字符的最长公共子序列的长度。然后根据字符串1和字符串2的字符是否相等来更新dp数组。具体的更新规则是,如果字符串1的第i个字符和字符串2的第j个字符相等,那么dp[i][j]就等于dp[i-1][j-1]+1;否则,dp[i][j]等于dp[i-1][j]和dp[i][j-1]中的较大值。最后,dp[m][n]就是最长公共子序列的长度,其中m和n分别表示字符串1和字符串2的长度。
相关问题
c++最长公共子序列
最长公共子序列问题是指给定两个字符串s1和s2,求它们的最长公共子序列(LCS)的长度。
解决该问题可以采用动态规划的思想,具体过程如下:
1. 定义状态:dp[i][j]表示s1的前i个字符与s2的前j个字符的LCS长度。
2. 初始化状态:dp[j]=dp[i]=0,表示空串与任意字符串的LCS长度都为0。
3. 状态转移方程:
当s1[i-1] = s2[j-1]时,dp[i][j] = dp[i-1][j-1] + 1;
当s1[i-1] ≠ s2[j-1]时,dp[i][j] = max(dp[i-1][j], dp[i][j-1])。
4. 最终结果:dp[m][n],其中m和n分别为s1和s2的长度。
以下是C++代码实现:
```
int longestCommonSubsequence(string text1, string text2) {
int m = text1.size(), n = text2.size();
vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
for(int i=1; i<=m; ++i) {
for(int j=1; j<=n; ++j) {
if(text1[i-1] == text2[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];
}
```
C++最长公共子序列问题代码
以下是一个求解最长公共子序列问题的 C 语言代码示例:
```c
#include <stdio.h>
#include <string.h>
#define MAX_LENGTH 100
int max(int a, int b) {
return (a > b) ? a : b;
}
int lcs(char* str1, char* str2, int len1, int len2) {
int dp[MAX_LENGTH][MAX_LENGTH];
for (int i = 0; i <= len1; i++) {
for (int j = 0; j <= len2; j++) {
if (i == 0 || j == 0)
dp[i][j] = 0;
else if (str1[i - 1] == str2[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[len1][len2];
}
int main() {
char str1[MAX_LENGTH], str2[MAX_LENGTH];
scanf("%s %s", str1, str2);
int len1 = strlen(str1);
int len2 = strlen(str2);
int result = lcs(str1, str2, len1, len2);
printf("The length of longest common subsequence is %d\n", result);
return 0;
}
```
这个程序中,函数 `lcs` 用于计算两个字符串的最长公共子序列。使用动态规划的思想,通过建立一个二维数组 `dp` 来保存中间结果。数组中的每个元素 `dp[i][j]` 表示字符串 `str1` 的前 `i` 个字符和字符串 `str2` 的前 `j` 个字符的最长公共子序列长度。如果 `str1[i-1] == str2[j-1]`,则当前字符在两个字符串中都存在,可以将最长公共子序列长度加一,否则将当前字符从其中一个字符串中去掉,取两种情况中的较大值作为最长公共子序列的长度。最终返回 `dp[len1][len2]`,即两个字符串的最长公共子序列长度。
注意事项:
- 本程序中的最长公共子序列要求不需要连续,如果需要连续,则需要改变动态规划的状态转移方程。
- 在输入字符串时,要保证字符串的长度不超过 `MAX_LENGTH`,否则可能会导致数组越界。
- 在实际应用中,为了避免字符串的长度过大,需要对算法进行优化,比如使用滚动数组等技巧。