alllcs.c

#include <stdio.h>
#include <assert.h>

#define SIZE 1010

int n = 0, m = 0;
char s[SIZE], t[SIZE];
int lcslen[SIZE][SIZE] = {};
int nexs[26][SIZE], next[26][SIZE];

int max(int a, int b) {
    return a >= b ? a : b;
}

int dfs(int si, int ti, int len, char* ans) {
    int i;
    int cnt = 0;
    if (lcslen[si][ti] == 0) {
        printf("%s\n", ans);
        return 1;
    }
    for (i = 0; i < 26; ++i) {
        int nsi = nexs[i][si] + 1;
        int nti = next[i][ti] + 1;
        if (nsi <= n && nti <= m && lcslen[nsi][nti] == lcslen[si][ti] - 1) {
            ans[len] = (char)('a' + i);
            cnt += dfs(nsi, nti, len + 1, ans);
            ans[len] = '\0';
        }
    }
    return cnt;
}

int main() {
    int i, j;
    int cnt;
    char ans[SIZE] = {};
    scanf("%s%s", s, t);
    while (s[n]) {
        assert('a' <= s[n] && s[n]  <= 'z');
        ++n;
    }
    while (t[m]) {
        assert('a' <= t[m] && t[m]  <= 'z');
        ++m;
    }
    assert(1 <= n && n <= 1000);
    assert(1 <= m && m <= 1000);
    for (i = 0; i < 26; ++i) {
        nexs[i][n] = n;
        for (j = n - 1; j >= 0; --j) {
            if (s[j] == 'a' + i)  {
                nexs[i][j] = j;
            }
            else {
                nexs[i][j] = nexs[i][j + 1];
            }
        }
        next[i][m] = m;
        for (j = m - 1; j >= 0; --j) {
            if (t[j] == 'a' + i)  {
                next[i][j] = j;
            }
            else {
                next[i][j] = next[i][j + 1];
            }
        }
    }
    for (i = n; i >= 0; --i) {
        for (j = m; j >= 0; --j) {
            if (i < n) {
                lcslen[i][j] = max(lcslen[i][j], lcslen[i + 1][j]);
            }
            if (j < m) {
                lcslen[i][j] = max(lcslen[i][j], lcslen[i][j + 1]);
            }
            if (i < n && j < m) {
                lcslen[i][j] = max(lcslen[i][j], lcslen[i + 1][j + 1] + (s[i] == t[j]));
            }
        }
    }
    cnt = dfs(0, 0, 0, ans);
    assert(1 <= cnt && cnt <= 2000);
    return 0;
}