算法：动态规划——最长公共子序列（LCS）

#include
#include
#include
using namespace std;

int main()
{
        string strx,stry;
cin>>strx>>stry;
int nx = strx.length();
int ny = stry.length();

vector> vecall;
for (int i=0;i<=nx;i++)
{
vector vec(ny+1,0);
vecall.push_back(vec);
}

for (int i=1;i<=nx;i++)
{
for (int j=1;j<=ny;j++)
{
if (strx[i-1]==stry[j-1])
{
vecall[i][j]=vecall[i-1][j-1]+1;
}
else if (vecall[i-1][j]>vecall[i][j-1])
{
vecall[i][j]=vecall[i-1][j];
}
else
{
vecall[i][j]=vecall[i][j-1];
}
}
}

int ans = vecall[nx][ny];//最长公共子序列长度
cout<
int i=nx;
int j=ny;
string lcs(ans,' ');
while (i && j)//找出最长公共子序列
{
if (strx[i-1]==stry[j-1] && vecall[i][j]==vecall[i-1][j-1]+1)
{
lcs[--ans]=strx[i-1];
i--,j--;
}
else if (vecall[i-1][j]>vecall[i][j-1])
{
i--;
}
else
{
j--;
}
}

for (i=0;i{
cout<}
return 0;
}