Fyn_Andersen通过本文主要向大家介绍了最长公共子序列等相关知识,希望对您有所帮助,也希望大家支持linkedu.com www.linkedu.com
Input示例
abcicba abdkscab
Output示例
abca
#include <iostream>
#include <cstring>
using namespace std;
int c[1001][1001], b[1001][1001];
void LSC(int n, int m, string x, string y)
{
int i, j;
for(i = 0; i <= n; i++)
c[i][0] = 0;
for(j = 0; j <= m; j++)
c[0][j] = 0;
for(i = 1; i <= n; i++)
{
for(j = 1; j <= m; j++)
{
if(x[i-1] == y[j-1])
{
c[i][j] = c[i-1][j-1] + 1;
b[i-1][j-1] = 0;
}
else
{
if(c[i-1][j] >= c[i][j-1])
{
c[i][j] = c[i-1][j];
b[i-1][j-1] = 1;
}
else{
c[i][j] = c[i][j-1];
b[i-1][j-1] = -1;
}
}
}
}
}
void S_LSC(string x, int i, int j)
{
if(i == 0 || j == 0)
return;
if(b[i-1][j-1] == 0)
{
S_LSC(x, i-1, j-1);
cout << x[i-1];
}
if(b[i-1][j-1] == 1)
{
S_LSC(x, i-1, j);
}
if(b[i-1][j-1] == -1)
{
S_LSC(x, i, j-1);
}
}
int main()
{
string x, y;
int n, m;
cin >> x >> y;
n = x.length();
m = y.length();
LSC(n, m, x, y);
S_LSC(x, n, m);
return 0;
}