c++实现最长公共子序列
时间: 2024-04-08 20:27:17 浏览: 20
C++可以通过动态规划算法来实现最长公共子序列(Longest Common Subsequence,简称LCS)。下面是一种常见的实现方式:
```cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int longestCommonSubsequence(string text1, string text2) {
int m = text1.length();
int n = text2.length();
// 创建一个二维数组dp,用于保存最长公共子序列的长度
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]) {
// 如果当前字符相等,则最长公共子序列长度加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 main() {
string text1 = "ABCBDAB";
string text2 = "BDCAB";
int result = longestCommonSubsequence(text1, text2);
cout << "最长公共子序列的长度为:" << result << endl;
return 0;
}
```
上述代码中,我们使用了一个二维数组`dp`来保存最长公共子序列的长度。通过两层循环遍历两个字符串的所有字符,如果当前字符相等,则最长公共子序列长度加1;如果当前字符不相等,则取前一个状态中的最大值。最终,`dp[m][n]`即为最长公共子序列的长度。