编辑代码

#include <bits/stdc++.h>
using namespace std;
int LCS_length(const string &str1, const string &str2, 
	            vector<vector<int> > &veca, vector<vector<int> > &vecb) {
	int i, j; 
	if (str1 == "" || str2 == "")
		return 0;
 
	for (i = 0; i <= str1.length(); i++) {
		veca[i][0] = 0;
	}
	for (j = 0; j <= str2.length(); j++) {
		veca[0][j] = 0;
	}
	for (i = 1; i <= str1.length(); i++) {
		for (j = 1; j <= str2.length(); j++) {

			if (str1[i - 1] == str2[j - 1]) {
				veca[i][j] = veca[i - 1][j - 1] + 1;
				vecb[i][j] = 1;
			}
			else {
				if (veca[i - 1][j] >= veca[i][j - 1]) {
					veca[i][j] = veca[i - 1][j];
					vecb[i][j] = 2;
				}
				else {
					veca[i][j] = veca[i][j-1];
					vecb[i][j] = 3; 
				}
			}
		}
	}
	return veca[str1.length()][str2.length()];
}
void PrintOneLCS(vector<vector<int> > &vecb, string &str1, string &str2, int i, int j) {
	if (i == 0 || j == 0)
		return;
	if (vecb[i][j] == 1) {
		PrintOneLCS(vecb, str1,str2, i - 1, j - 1);
		cout << str1[i - 1];  
	}
	else if (vecb[i][j] == 2)
		PrintOneLCS(vecb, str1, str2, i -1, j);
	else
		PrintOneLCS(vecb, str1, str2, i, j - 1);
}
 
int main() {
	string input;
	getline(cin, input);
	stringstream ss(input);
	string str1, str2;
	ss >> str1;
	ss >> str2;
	vector<vector<int> > veca(str1.length() + 1, vector<int>(str2.length() + 1));
	vector<vector<int> > vecb(str1.length() + 1, vector<int>(str2.length() + 1));
	cout << LCS_length(str1, str2, veca, vecb) << endl;
	PrintOneLCS(vecb, str1, str2, str1.length(), str2.length());
	return 0;
}