最长公共子序列

最长公共子序列问题:给定两个序列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得到

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏tkokof 的技术,小趣及杂念

编程小知识之 Random接口返回值

平日工作中,(伪)随机数的使用一定是避不开的,拿 C# 为例,System 命名空间下的 Random 类型一般都是我们生成(伪)随机数的第一选择:

963
来自专栏bboysoul

1493: C语言实验题――圆柱体计算

描述:已知圆柱体的底面半径r和高h,计算圆柱体底面周长和面积、圆柱体侧面积以及圆柱体体积。 输入:输入数据有一行,包括2个正实数r和h,以空格分隔。 输出:...

791
来自专栏Python小屋

使用Python列表实现向量运算

在Python中,列表支持与整数的乘法运算,但表示的是列表元素的重复,并生成新列表,如: >>> [1,2,3]*3 [1, 2, 3, 1, 2, 3, 1...

4946
来自专栏数据结构与算法

1116 四色问题

1116 四色问题  时间限制: 1 s  空间限制: 128000 KB  题目等级 : 黄金 Gold 题解 题目描述 Description 给定N(小于...

2845
来自专栏Leetcode名企之路

【Leetcode】81. 搜索旋转排序数组 II

( 例如,数组 [0,0,1,2,2,5,6] 可能变为 [2,5,6,0,0,1,2] )。

1652
来自专栏企鹅号快讯

Python排序(一)

“为了学习Python编程,通过Python编写了一些算法小程序,作为自己的学习笔记,同时分享给大家共同学习交流!” 现在计算机的广泛使用使得数据无处不在, 而...

2005
来自专栏尾尾部落

[算法总结] 二分查找

二分查找法作为一种常见的查找方法,将原本是线性时间提升到了对数时间范围,大大缩短了搜索时间,但它有一个前提,就是必须在有序数据中进行查找。

2052
来自专栏desperate633

LintCode 搜索旋转排序数组题目分析代码

假设有一个排序的按未知的旋转轴旋转的数组(比如,0 1 2 4 5 6 7 可能成为4 5 6 7 0 1 2)。给定一个目标值进行搜索,如果在数组中找到目标值...

1062
来自专栏Python小屋

奇怪,有的Python函数或方法调用需要两对括号?

本文源自于一位读者的问题:为啥有的函数或方法调用要使用两对括号呢? 但是在我的印象里并没有这种用法啊。于是我简单扫了一眼代码,发现这位朋友说的并不是函数调用需要...

3015
来自专栏WD学习记录

数据结构与算法2016-05-31

数据元素是数据的基本单位,在计算机程序中通常被作为一个整体进行考虑和处理。一个数据元素可由若干个数据项组成。数据项是不可分割的、含有独立意义的最小数据单位,数据...

1072

扫码关注云+社区

领取腾讯云代金券