采用动态规划法编程实现最长公共子序列算法
#include<iostream>#include<cstdlib>
using namespace std;
const int Total=1000;
void SuiJi(char A[Total])
{
for(int j=0;j<Total;j++)
{
A[j]=rand()%26+97; //产生随机字符
}
}
void LCSLLength(int m,int n,char*x,char*y,int c[Total][Total],int b[Total][Total])
{
int i,j;
for(i=0;i<m;i++) c[i][0]=0;
for(i=0;i<n;i++) c[0][i]=0;
for(i=0;i<m;i++)
for(j=0;j<n;j++)
{
if(x[i]==y[j])
{
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
{
c[i][j]=c[i][j-1];b[i][j]=3;
}
}
}
void LCS(int i,int j,char*x,int b[Total][Total])
{
if(i==0||j==0)return;
if(b[i][j]==1)
{
LCS(i-1,j-1,x,b);
cout<<x[i]<<' ';
}
else if(b[i][j]==2)
{
LCS(i-1,j,x,b);
}
else
{
LCS(i,j-1,x,b);
}
}
int main()
{
char X[Total];
char Y[Total];
int c[Total][Total],b[Total][Total];
SuiJi(X);
SuiJi(Y);
LCSLLength(Total,Total,X,Y,c,b);
LCS(Total,Total,X,b);
return 0;
}
代码可以运行,但是为什么没显示出结果,求大神指点