关于这道题在 blog 有详细的解释
#include <iostream>
#include <string>
#include <vector>
using namespace std;
vector<vector<int>> LCS_helper(const string &str1, const string &str2)
{
int i, j;
vector<vector<int>> dp(str1.length() + 1, vector<int>(str2.length() + 1));
if (str1 == "" || str2 == "")
return dp;
for (i = 1; i <= str1.length(); i++)
{
for (j = 1; j <= str2.length(); j++)
{
if (str1[i - 1] == str2[j - 1])
{
dp[i][j] = dp[i - 1][j - 1] + 1;
}
else
{
if (dp[i - 1][j] >= dp[i][j - 1])
{
dp[i][j] = dp[i - 1][j];
}
else
{
dp[i][j] = dp[i][j - 1];
}
}
}
}
return dp;
}
string getLCS(string str1, string str2, vector<vector<int>> dp)
{
string lcs;
int i = str1.length(), j = str2.length();
while (i > 0 && j > 0)
{
if (str1[i - 1] == str2[j - 1])
{
lcs = str1[i - 1] + lcs;
--i;
--j;
}
else
{
if (dp[i - 1][j] >= dp[i][j - 1])
--i;
else
--j;
}
}
return lcs;
}
string getLCSS(string str1, string str2, vector<vector<int>> dp)
{
string lcss;
int i = str1.length(), j = str2.length();
while (i > 0 && j > 0)
{
cout << str1[i - 1] << " | " << str2[j - 1] << endl;
if (str1[i - 1] == str2[j - 1])
{
lcss = str1[i - 1] + lcss;
--i;
--j;
}
else
{
if (dp[i - 1][j] >= dp[i][j - 1])
{
lcss = str1[i - 1] + lcss;
--i;
}
else
{
lcss = str[j - 1] + lcss;
--j;
}
}
}
cout << lcss << " | " << i << " | " << j << endl;
if (i > 0)
lcss = str1.substr(0, i) + lcss;
if (j > 0)
lcss = str2.substr(0, j) + lcss;
return lcss;
}
string shortestCommonSupersequence(string str1, string str2)
{
}
int main(void)
{
string str1 = "adbcbccdcadcbcbcbbdccbddcdccababccbccbddbbbcabdbdacdbccccbabacaa", str2 = "dcbaddabcaadabacbbbddccbbccdbadbdaccdccbbbdbddcbacbdbcdcaddbdadabcbaacbaaaaadbcba";
vector<vector<int>> d = LCS_helper(str1, str2);
cout << getLCSS(str1, str2, d) << endl;
return 0;
}