解题思路

问题分析

最长公共子序列（LCS）长度计算：首先求出两条序列的 LCS 长度，确定最长共同路线的长度。 回溯所有最长公共子序列：在计算 LCS 长度的同时，记录转移路径，回溯所有可能的最长子序列。 去重与排序：对回溯得到的子序列去重，并按字典序排序后输出。

关键步骤 动态规划表构建：使用二维数组dp[i][j]表示爱丽丝前i个字符和鲍勃前j个字符的 LCS 长度。 路径记录：在填充dp表时，记录每个状态的转移方向（来自左上、左或上），用于回溯。 回溯生成子序列：从dp[m][n]（m、n为两条序列长度）开始，根据转移方向回溯，收集所有可能的字符组合。 去重与排序：使用集合（Set）存储子序列以自动去重，最后转换为列表并排序。 算法优化 记忆化回溯：通过记录转移方向，避免重复计算，高效生成所有 LCS。 字典序排序：利用字符串的字典序特性，直接对结果列表排序。 #include #include #include #include using namespace std; int n,m,f[105][105],na[105][26],nb[105][26]; char a[105],b[105]; string res[1005]; int cnt; void dfs(int i,int j,string s,int nd) { if(nd==0) { res[cnt++]=s; return; } if(i>n||j>m) return; if(a[i]==b[j]) { string t=s+a[i]; dfs(i+1,j+1,t,nd-1); return; } for(int v=0;v<26;v++) if(f[na[i-1][v]][nb[j-1][v]]==nd) dfs(na[i-1][v]+1,nb[j-1][v]+1,s,nd); } int main() { #ifdef local freopen("pro.in","r",stdin); #endif scanf("%s%s",a+1,b+1); n=strlen(a+1); m=strlen(b+1); for(int i=n;i>=1;i--) for(int j=m;j>=1;j--) { if(a[i]==b[j]) f[i-1][j-1]=f[i][j]+1; else f[i-1][j-1]=max(f[i][j-1],f[i-1][j]); } for(int j=0;j<26;j++) { na[n][j]=n; nb[m][j]=m; } for(int i=n;i>=1;i--) for(int j=0;j<26;j++) if(a[i]==j+'a') na[i-1][j]=i-1; else na[i-1][j]=na[i][j]; for(int i=m;i>=1;i--) for(int j=0;j<26;j++) if(b[i]==j+'a') nb[i-1][j]=i-1; else nb[i-1][j]=nb[i][j]; dfs(1,1,"",f[0][0]); sort(res,res+cnt); for(int i=0;i<cnt;i++) printf("%s\n",res[i].c_str()); return 0; }