[골4] 9252 - LCS 2

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    string str1, str2;
    cin >> str1 >> str2;
    str1 = ' ' + str1;
    str2 = ' ' + str2;
    int n = str1.size(), m = str2.size();
    vector<vector<int>> v(n, vector<int>(m));
    stack<char> s;

    for (int i = 1; i < n; i++)
    {
    	for (int j = 1; j < m; j++)
    	{
            if (str1[i] == str2[j])
                v[i][j] = v[i - 1][j - 1] + 1;

            else
                v[i][j] = max(v[i - 1][j], v[i][j - 1]);
    	}
    }
    auto col = n - 1, row = m - 1;
    
    cout << v[col][row] << endl;
    string res = "";

    while (v[col][row])
    {
        if (v[col][row] == v[col - 1][row])
            col--;

        else if (v[col][row] == v[col][row - 1])
            row--;

        else
        {
            res += str1[col--];
            row--;
        }
    }
    if (!res.empty())
    {
        reverse(res.begin(), res.end());
        cout << res << endl;
    }
}