统计LCS方案并输出。
好烦啊,记录一下上一个同样的字符出现的位置,因为要匹配,如果不选择上一个,一定不是最优的。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<iostream>
#include<vector>
using namespace std;
const int N=81;
char s[N];
int a[N],b[N],n,m;
int f[N][N];
int lasta[N][30],lastb[N][30];
/*
    记录从1到i中,第j个字符出现的最晚位置。
    如果不是最晚位置,那么一定不是最优解。
    然后逐字扫描,判断是否可行。 
*/
vector<string>ans;
void dfs(int x,int y,string now,int len)
{
    if(!len){ans.push_back(now);return ;}
    if(x<1||y<1)return ;
    for(int i=1;i<=26;i++)
    {
        int t1=lasta[x][i],t2=lastb[y][i];
        char c='a'+i-1;
        if(f[t1][t2]==len)//a[t1]==b[t2],且f[t1][t2]之前的状态均小于len(有一些是len-1) 
            dfs(t1-1,t2-1,c+now,len-1);
    }
}
int main()
{
    scanf("%s",s+1);n=strlen(s+1);
    for(int i=1;i<=n;i++)a[i]=s[i]-'a'+1;
    scanf("%s",s+1);m=strlen(s+1);
    for(int i=1;i<=m;i++)b[i]=s[i]-'a'+1;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(a[i]!=b[j])
                f[i][j]=max(f[i-1][j],f[i][j-1]);
            else
                f[i][j]=f[i-1][j-1]+1;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=26;j++)
        {
            if(a[i]!=j)lasta[i][j]=lasta[i-1][j];
            else lasta[i][j]=i;
        }
    for(int i=1;i<=m;i++)
        for(int j=1;j<=26;j++)
        {
            if(b[i]!=j)lastb[i][j]=lastb[i-1][j];
            else lastb[i][j]=i; 
        }
    dfs(n,m,"",f[n][m]);
    sort(ans.begin(),ans.end());
    for(int i=0;i<ans.size();i++)
        cout<<ans[i]<<endl;
    return 0;
}