LCS O(n*m) + print all

#include <bits/stdc++.h>
using namespace std;

#define ll long long

string a, b;
int n, m;

int lcs[1001][1001]; //length of lcs
set <string> set_lcs; //all distinct lcs

void find_lcs(int n, int m, string s)
{
    if (n == 0 or m == 0)
    {
        set_lcs.insert(s);
        return;
    }

    if (a[n-1] == b[m-1])
    {
        s = a[n-1] + s;
        find_lcs(n-1, m-1, s);
    }
    else
    {
        if (lcs[n-1][m] >= lcs[n][m-1])
            find_lcs(n-1, m, s);
        if (lcs[n-1][m] <= lcs[n][m-1])
            find_lcs(n, m-1, s);
    }
}

int main()
{

    cin >> a >> b;
    n = a.size(), m = b.size();

    for (int i = 1; i<=n; i++)
    {
        for (int j = 1; j<=m; j++)
        {
            if (a[i-1] == b[j-1]) lcs[i][j] = lcs[i-1][j-1]+1;
            else lcs[i][j] = max(lcs[i-1][j], lcs[i][j-1]);
        }
    }

    find_lcs(n, m, "");
    cout << "LCS length is " << lcs[n][m] << endl
         << "LCS number is " << set_lcs.size() << endl;
    for (auto &s : set_lcs)
        cout << s << " ";
}