关于这道题在 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;
}