C++(g++ 7.5.0) 解法, 执行用时: 4ms, 内存消耗: 688K, 提交时间: 2022-08-13 13:59:12

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef string str;
#define MAXN 211
ll f[MAXN][MAXN],la,lb;
char a[MAXN],b[MAXN];
ll loca[29][MAXN],locb[29][MAXN];
std::vector<str>res;
void printway(ll i,ll j,ll rest,str cur)
{
    if(!rest)
    {
        res.push_back(cur);
        return;
    }
    if(!i||!j)return;
    for(ll k=0;k<26;++k)
    {
        ll pi=loca[k][i],pj=locb[k][j];
        if(f[pi][pj]==rest)printway(pi-1,pj-1,rest-1,char('a'+k)+cur);
    }
}
int main()
{
    scanf("%s%s",a+1,b+1);
    la=strlen(a+1),lb=strlen(b+1);
    f[0][0]=0;
    for(ll i=1;i<=la;++i)
        for(ll j=1;j<=lb;++j)
        {
            ll cur=max(f[i-1][j],f[i][j-1]);
            if(a[i]==b[j])cur=f[i-1][j-1]+1;
            f[i][j]=cur;
        }
    for(ll i=1;i<=la;++i)
        for(ll j=0;j<26;++j)
            if(a[i]=='a'+j)loca[j][i]=i;
            else loca[j][i]=loca[j][i-1];
    for(ll i=1;i<=lb;++i)
        for(ll j=0;j<26;++j)
            if(b[i]=='a'+j)locb[j][i]=i;
            else locb[j][i]=locb[j][i-1];
    printway(la,lb,f[la][lb],"");
    std::sort(res.begin(),res.end());
    for(std::vector<str>::iterator it=res.begin();it!=res.end();++it)
        std::cout<<*it<<endl;
    return 0;
}

C++ 解法, 执行用时: 13ms, 内存消耗: 768K, 提交时间: 2022-01-30 14:25:44

#include<bits/stdc++.h>
using namespace std;
string s,t;
int f[1001][1001],n,m;
set<string>h;
void dfs(int k,int n,int m,string ss){
    if(!k){reverse(ss.begin(),ss.end());h.insert(ss);return;}
    for(int i=1;i<n;i++)for(int j=1;j<m;j++)if(s[i-1]==t[j-1]&&f[i][j]==k)ss.push_back(s[i-1]),dfs(k-1,i,j,ss),ss.pop_back();
}
int main(){
    cin>>s>>t;
    n=s.size(),m=t.size();
    for(int i=0;i<n;i++)for(int j=0;j<m;j++){f[i+1][j+1]=max(f[i+1][j],f[i][j+1]);if(s[i]==t[j]&&f[i][j]+1>=f[i+1][j+1])f[i+1][j+1]=f[i][j]+1;}
    dfs(f[n][m],n+1,m+1,"");
    for(auto it:h)cout<<it<<"\n";
    return 0;
}