| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 595 人关注过本帖
标题:最长公共子序列
只看楼主 加入收藏
没事跳楼耍
Rank: 1
等 级:新手上路
帖 子:20
专家分:0
注 册:2007-3-19
收藏
 问题点数:0 回复次数:0 
最长公共子序列

以下是求两个序列的最长公共子序列的程序
为什么总是的不到最长的公共子序列,请大家一起帮忙修改一下,我看了很久也没发现什么问题
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;
}

搜索更多相关主题的帖子: 序列 
2007-11-08 15:10
快速回复:最长公共子序列
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.100436 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved