以下是求两个序列的最长公共子序列的程序
为什么总是的不到最长的公共子序列,请大家一起帮忙修改一下,我看了很久也没发现什么问题
S_TABLE lcs_length(string x,string y){//x,y分别是具有m个和n个字符的字符串,b是记录匹配信息的矩阵
unsigned long i,j,m=x.size(),n=y.size();
I_TABLE c(m+1,n+1);
S_TABLE b(m+1,n+1);
for(i=1;i<=m;i++)//当串y为空串时,最长公共子串亦为空串
c[i][0]=0;
for(j=0;j<=n;j++)//当串x为空串时,最长公共子串亦为空串
c[0][j]=0;
for(i=1;i<=m;i++)//自底向上地对x,y的所有前缀扫描
for(j=1;j<=n;j++){
for(j=1;j<=n;j++){
if(x[i]==y[j]){
c[i][j]=c[i-1][j-1]+1;
b[i][j]="incline";//incline指示出公共元素
}
else if(c[i-1][j]>=c[i][j-1]){
c[i][j]=c[i-1][j];
b[i][j]="up";//up指示出x中无效的元素
}
else{
c[i][j]=c[i][j-1];
b[i][j]="flat";//flat指示出y中无效的元素
}
}
}
//cout<<c<<endl<<b<<endl;
return b;
}
void print_lcs(S_TABLE b,string x,int i,int j){//b是记录匹配信息的矩阵,x是第一个字符串,i,j分别是x,y前缀的串长,n是y的串长
if(i==0||j==0)
return;
if(b[i][j]=="incline"){
print_lcs(b,x,i-1,j-1);
cout<<x[i];
}
else if(b[i][j]=="up")
print_lcs(b,x,i-1,j);
else
print_lcs(b,x,i,j-1);
}
int main(){
string x("abcbdab"),y("bdcaba");
Table<string> b(8,7);
b=lcs_length(x,y);
print_lcs(b,x,7,6);
cout<<endl;
return 0;
}