博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
最长公共子序列
阅读量:7099 次
发布时间:2019-06-28

本文共 867 字,大约阅读时间需要 2 分钟。

最长公共子序列问题:给定两个序列X={x1,x2,....xm},    Y={y1,y2,yn},找出XY的最长公共子序列

1 最长公共子序列结构

  1 xm=yn,则zk = xm = yn,且zk-1是xm-1和yn-1的最长公共子序列

  2 xm!=yn,zk!=xm,则Z是xm-1,yn的最长共公共子序列

  3 xm!=yn,zk!=yn,则Z是xm,yn-1的最长公共子序列

2 子问题的递归结构

  1 xm=yn时,找出xm-1,yn-1的最长公共子序列

  2 xm!=yn时,找出xm 和 yn-1     或者   xm-1和yn的最长公共子序列

3 计算最优值

c[i][j]:存储xi,yj的最长公共子序列长度

b[i][j]:记录c[i][j]的值是由哪一个子问题的解得到的 

void LCSLength(int m,int n,char* x,int * * c,int * *b){int i,j;for(i=1;i<=m;i++)    c[i][0] = 0;for(i=1;i<=m;i++)    c[o][i] = 0;for(i=1;i<=m;i++)  for(j=1;j<=n;j++){     if(x[i] == y[j]){          c[i][j] = c[i-1][j-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;      }} }

耗时O(mn);

4 构造最长公共子序列

b[m][n]开始:

  值为1:由xm-1,yn-1得到

  值为2:由xm-1,yn得到

  值为3:由xm,yn-1得到

本文转自博客园xingoo的博客,原文链接:,如需转载请自行联系原博主。
你可能感兴趣的文章
loadrunner web_custom_request 脚本处理
查看>>
【中文】Joomla1.7扩展介绍之Sitelinkx (自动链接)
查看>>
上下文菜单点击获取ContextMenu实例方法
查看>>
【转】Entity Framework6 with Oracle(可实现code first)
查看>>
6 Spring Boot 静态资源处理
查看>>
MyEclipse8.6启动后提示内存不足的解决方案(亲测,完美解决)
查看>>
架构设计:生产者/消费者模式
查看>>
最小花费
查看>>
【Unity3D】Unity3D之 Resources.Load 动态加载资源
查看>>
使用jmeter进行简单的压测
查看>>
创建逻辑卷
查看>>
Ubuntu安装显卡驱动+cuda8+cudnn
查看>>
SSH: sshd dead but subsys locked
查看>>
被孟加拉题吊打的ACM考试
查看>>
git 使用命令
查看>>
D90四种对焦点模式
查看>>
mac下SVN上传.a静态库文件
查看>>
mikadonic-自动创建挂载本地YUM镜像
查看>>
Flutter 安装
查看>>
Linux - 静默安装oracle数据库总结
查看>>