AcWing 897. 如何记录最长公共子序列
原题链接
简单
作者:
惊蛰雨
,
2024-04-01 22:15:45
,
所有人可见
,
阅读 1
/*
如何记录最长公共子序列,只需要将每一次寻找子序列
时记录子序列由哪个子序列来,也就是从哪个方向,并
且当两个子序列相等时,s1[i] = s2[j],开辟一个数组
记录下来
因为最长子序列存储值存储在dp[n][m],所以我们由
dp[n][m]逆向寻找即可
我们发现可能由多个最长子序列,在这里我们强制规
定当dp[i - 1][j] = dp[i][j - 1]时从dp[i - 1][j]
来,也就是从左上角来
我们规定当s[i] = s[j]时g[i][j] = 0,表示从左上角
来,1表示从上方来也就是dp[i-1][j],2表示从左方来
也就是dp[i][j - 1]
*/
# include <iostream>
# include <cstring>
# include <cstdio>
# include <algorithm>
using namespace std;
const int N = 1010;
int n, m;
char s1[N], s2[N];
int dp[N][N];
int g[N][N];
char s[N];//记录此时的字符
int t = 0;
void dfs(int i, int j)
{
if(i == 0 || j == 0) return ;//表示遍历结束
if(g[i][j] == 0)//只有当g[i][j]==0时才表示当前两个字符是相同的也就是s1[i] = s2[j],记录此时的字符即可
{
s[t ++] = s1[i];//两个字符相同记录任何一个就可以
dfs(i - 1, j - 1);//代表从左上角来,回到左上角即可
}
else if(g[i][j] == 1)
dfs(i - 1, j);//如果为1说明是从i-1,j或者i-1,j-1中来,由于dp[i-1][j]包含dp[i-1][j-1]
//跳到当前这个子序列寻找相同的两个字符
else
dfs(i, j - 1);
}
int main ()
{
scanf("%d%d", &n, &m);
scanf("%s%s", s1 + 1, s2 + 1);
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= m; j ++)
{
if(s1[i] == s2[j])
{
dp[i][j] = dp[i - 1][j - 1] + 1;
g[i][j] = 0;//零表示从左上来并且表示当前两个字符相同
}
else
{
if(dp[i - 1][j] >= dp[i][j - 1])
{
dp[i][j] = dp[i - 1][j];
g[i][j] = 1;//表示从上面或者左上来也就是i - 1,j的子序列和i-1,j-1的子序列
//以及规定如果两个子序列长度相等,规定一律从上方来
}
else
{
dp[i][j] = dp[i][j - 1];
g[i][j] = 2;//表示从右边来也就是i,j-1的序列
}
}
}
dfs(n, m);
cout<< dp[n][m]<< endl;
for(int i = t - 1; i >= 0; i --)
cout<< s[i]<< " ";
puts("");
return 0;
}