#include <stdio.h>
#include <string>
#include"iostream"
using namespace std;
void LCS_L(string x,string y,int **b)
{
int i,j;
int m = x.size();
int n = y.size();
int **c;
c = new int*[m+1];
for(i = 0;i < m+1;i++)
c[i] = new int[n+1];
for (i=0;i<=m;i++) c[i][0] = 0;
for (i=1;i<=n;i++) c[0][i] = 0;
for (i=1;i<=m;i++)
for (j=1;j<=n;j++)
{
if (x[i-1] == y[j-1])
{
c[i][j] = c[i-1][j-1] + 1;
b[i][j] = 1;
}
else if (c[i-1][j] > c[i][j-1])
{
c[i][j] = c[i-1][j];
b[i][j] = 2;
}
else if (c[i-1][j] < c[i][j-1])
{
c[i][j] = c[i][j-1];
b[i][j] = 3;
}
else
{
c[i][j] = c[i][j-1];
b[i][j] = 4;
}
}
for(i = 0;i < m+1;i++)
delete c[i];
delete c;
}
void LCS_L_Output(int i,int j,string x,int **b,int &length,int &index,char z[])
{
if (i==0||j==0)
{
length =index+1;
for(int i=index;i>=0;i--)
cout<<z[i];
cout<<endl;
return ;
}
if (b[i][j]==1)
{
z[++index]=x[i-1];
LCS_L_Output(i-1,j-1,x,b,length,index,z);
--index;
}
else if (b[i][j]==2)
{
LCS_L_Output(i-1,j,x,b,length,index,z);
}
else if (b[i][j]==3)
{
LCS_L_Output(i,j-1,x,b,length,index,z);
}
else
{
LCS_L_Output(i-1,j,x,b,length,index,z);
LCS_L_Output(i,j-1,x,b,length,index,z);
}
}
int main()
{
string x="abcbdab";string y="bdcaba";
int **b;
int length=0;
int index=-1;
char z[10];
memset(z,0,10);
int m = x.size();
int n = y.size();
b = new int*[m+1];
for(int i = 0;i < m+1;i++)
b[i] = new int[n+1];
LCS_L(x,y,b);
cout << "最长公共序列:"<<endl;
LCS_L_Output(m,n,x,b,length,index,z);
cout << "\n长度 :" << length << endl;
for(i = 0;i < m+1;i++)
delete b[i];
delete b;
return 0;
}
