最长公共子序列记录路径
作者:
wylTUN
,
2022-12-06 20:39:44
,
所有人可见
,
阅读 183
最长公共子序列记录路径
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 1010;
int n,m,dp[N][N];
char str1[N],str2[N];
char step[N][N],ans[N];
int main() {
gets(str1);
gets(str2);
n = strlen(str1);
m = strlen(str2);
for(int i = 0; i < n; i++) {
if(str1[i] == str2[0]) step[i][0] = 'd',dp[i][0] = 1;
else step[i][0] = 'u',dp[i][0] = dp[i - 1][0];
}
for(int i = 0; i < m; i++) {
if(str1[0] == str2[i]) step[0][i] = 'd',dp[0][i] = 1;
else step[0][i] = 'l',dp[0][i] = dp[0][i - 1];
}
for(int i = 1; i < n; i++) {
for(int j = 1; j < m; j++) {
if(dp[i - 1][j] > dp[i][j - 1]) {
dp[i][j] = dp[i - 1][j];
step[i][j] = 'u'; //从上面来的
}
else {
dp[i][j] = dp[i][j - 1];
step[i][j] = 'l'; //从左边来的
}
if(str1[i] == str2[j]) {
step[i][j] = 'd'; //对角线
dp[i][j] = max(dp[i - 1][j - 1] + 1,dp[i][j]);
}
}
}
int len = dp[n - 1][m - 1]; //回溯找答案
int tmp = len;
for(int i = n - 1,j = m - 1; tmp;) {
if(step[i][j] == 'd') {
ans[tmp--] = str1[i];
i--;
j--;
}
else if(step[i][j] == 'u') i--;
else j--;
}
for(int i = 1; i <= len; i++) printf("%c",ans[i]);
puts("");
return 0;
}