#include<iostream>
#include<vector>
#include<string>
#include<iomanip>
using namespace std;
vector<vector<int>>b;
int dp(vector<vector<int>>&b,string &x1, string &x2)
{
int m, n;
m=x1.length();
n = x2.length();
vector<vector<int>>dp(m + 1, vector<int>(n + 1));
for (int i = 0; i < m; i++)
dp[i][0] = 0;
for (int j = 0; j < n; j++)
dp[0][j] = 0;
for (int i = 1; i <= m; i++)
{
for (int j = 1; j <= n; j++)
{
if (x1[i - 1] == x2[j - 1])
{
dp[i][j] = dp[i - 1][j - 1] + 1;
b[i][j] = 1;
}
else
{
if (dp[i - 1][j] > dp[i][j - 1])
{
dp[i][j] = dp[i - 1][j];
b[i][j] = 2;
}
else
{
dp[i][j] = dp[i][j - 1];
b[i][j] = 3;
}
}
}
}
return dp[m][n];
}
void search(vector<vector<int>>& b, int i, int j, string& x1)
{
if (i == 0 || j == 0)
return;
if (b[i][j] == 1)
{
cout << x1[i - 1] << " ";
search(b, i - 1, j - 1, x1);
//cout << x1[i-1] << " ";
}
else if (b[i][j] == 2)
search(b, i - 1, j,x1);
else
search(b, i, j - 1,x1);
}
int main()
{
string x1, x2;
x1 = "abcdefdd";
x2 = "abdefs";
int m, n;
m = x1.length();
n = x2.length();
b = vector<vector<int>>(m + 1, vector<int>(n + 1,0));
for (int i = 0; i <= m; i++)
{
for (int j = 0; j <= n; j++)
cout << setw(5) << b[i][j];
cout << endl;
}
cout<<dp(b, x1, x2)<<endl;
search(b,m,n,x1);
cout << endl;
for (int i = 0; i <= m; i++)
{
for (int j = 0; j <= n; j++)
cout << setw(5) << b[i][j];
cout << endl;
}
return 0;
}
