如何使用C++中的最长公共子序列算法
最长公共子序列(Longest Common Subsequence,简称LCS)是一种常见的字符串匹配问题,用于寻找两个字符串中最长的相同子序列。在C++中,我们可以使用动态规划(Dynamic Programming)来解决LCS问题。
下面是一个C++代码示例,演示了如何使用最长公共子序列算法:
#include <iostream>
#include <vector>
#include <string>
using namespace std;
string longestCommonSubsequence(string text1, string text2) {
int m = text1.size();
int 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++) {
// 如果当前字符相等,则在之前的基础上加1
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]);
}
}
}
// 根据dp数组构建最长公共子序列
int i = m;
int j = n;
string lcs = "";
while (i > 0 && j > 0) {
if (text1[i-1] == text2[j-1]) {
// 如果当前字符相等,则将字符加入最长公共子序列中
lcs = text1[i-1] + lcs;
i--;
j--;
} else {
// 如果当前字符不相等,则根据dp数组移动指针
if (dp[i-1][j] >= dp[i][j-1]) {
i--;
} else {
j--;
}
}
}
return lcs;
}
int main() {
string text1 = "ABCD";
string text2 = "ACDF";
string lcs = longestCommonSubsequence(text1, text2);
cout << "最长公共子序列为:" << lcs << endl;
return 0;
}
上述代码中,我们首先使用动态规划来构建一个二维数组dp
,其中dp[i][j]
表示text1
的前i
个字符和text2
的前j
个字符所构成的最长公共子序列的长度。然后,我们根据动态规划的结果,利用dp
数组构建最长公共子序列。最后,输出最长公共子序列即可。