Gọi $f_{i, j}$ là độ dài xâu con chung dài nhất xâu $S1(i)$ ($i$ kí tự đầu của $S1$) và xâu $S2(j)$ ($j$ kí tự đầu của $S2$)

Công thức truy hồi:

$\left \{ {{f_{i, j}=f_{i-1, j-1} \text{+1 Nếu } S1_i=S2_j} \atop {f_{i, j}=max(f_{i, j-1}, f_{i-1, j}) \text{ Nếu } S1_i!=S2_j}} \right.$

Cơ sở: $f_{0, j} = f_{i, 0} = 0$

Code C++: 

#include<bits/stdc++.h>
#define int int64_t
using namespace std;
string a, b, s;
int f[260][260], m, n, k;
signed main()
{
 ios::sync_with_stdio(0);
 cin.tie(0); cout.tie(0);
 cin >> a >> b;
 m = a.size();
 n = b.size();
 a = ' ' + a;
 b = ' ' + b;
 for (int i = 1; i <= m; ++i)
    {
        for (int j = 1; j <= n; ++j)
        {
            if(a[i] == b[j])
            {
                f[i][j] = f[i - 1][j - 1] + 1;
            }
            else
            {
                f[i][j] = max(f[i - 1][j], f[i][j - 1]);
            }
        }
    }
    k = f[m][n];
    s = "";
    while (k > 0)
    {
        if(a[m] == b[n])
        {
            s = a[m] + s;
            k--; m--; n--;
        }
        else
        {
            if(f[m - 1][n] == k) m--;
            if(f[m][n - 1] == k) n--;
        }
    }
    cout << s.size() << '\n' << s;
 return 0;
}