一眼看去,唔,LCS裸题.等一下,输出具体方案?!!
于是这就变成了一个毒瘤题.
好,众所周知LCS是这样做的:$$f[i][j]=f[i-1][j-1]\ (a[i]==b[j])$$
$$f[i][j]=max(f[i-1][j],f[i][j-1])$$
接下来考虑输出方案数:
找两个a,b中的相同字符,记位置为$pi,pj$然后递归处理$pi,pj$之前的段,直到某个串为空.
可以预处理出$loca[k][i]$表示字符$k$在A串前$i$个字符中最后一次出现的位置.$locb$同理.
找相同字符就可以优化成枚举字符$k,pi=loca[k][i],pj=locb[k][j]$
最后把所有的串排序.
时间复杂度玄学.
/**********/
typedef long long ll;
typedef std::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];
//printf("%lld\n",f[la][lb]);
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<<std::endl;
return 0;
不是f[i][j]=f[i−1][j−1]+1 (a[i]==b[j])吗