LCS问题

时间:2023-03-08 17:42:37

最长公共子序列问题

1。这里pre数组表示回溯的方式,状态转移方程!!!

#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#pragma warning(disable:4996)
using namespace std; char a[];
char b[];
int dp[][];
int pre[][]; void dfs(int m,int n)
{
if(m==||n==)
return;
if(pre[m][n]==)
{
dfs(m-,n-);
cout<<a[m];
}
else if(pre[m][n]==)
{
dfs(m-,n);
}
else
{
dfs(m,n-);
}
} int main()
{
int i,j,len1,len2;
memset(dp,,sizeof(dp));
memset(pre,,sizeof(pre)); cin>>a+>>b+; len1=strlen(a+);
len2=strlen(b+); for(i=;i<=len1;i++)
{
for(j=;j<=len2;j++)
{
if(a[i]==b[j])
{
dp[i][j]=dp[i-][j-]+;
pre[i][j]=;
}
else
{
if(dp[i-][j]>dp[i][j-])
{
dp[i][j]=dp[i-][j];
pre[i][j]=;
}
else
{
dp[i][j]=dp[i][j-];
pre[i][j]=;
}
}
}
}
dfs(len1,len2);
cout<<endl;
return ;
}