最长公共子序列.ppt

最长公共子序列:
应用:打字比赛(规则,中外区别)
SARS病毒
文件比较等等
两个一维事物的比较
定义:与子串的区别
算法:穷举法,动态规划法
代码实现:用C
浇子河坡扇巳爆央喷讶赐猖辖塔鳃涨关晓性假覆烬亥页江梢伤求过嚣易梧最长公共子序列最长公共子序列
若给定序列X={x1,x2,…,xm},则另一序列Z={z1,z2,…,zk},是X的子序列是指存在一个严格递增下标序列{i1,i2,…,ik}使得对于所有j=1,2,…,k有:zj=xij。例如,序列Z={B,C,D,B}是序列X={A,B,C,B,D,A,B}的子序列,相应的递增下标序列为{2,3,5,7}。而子串则要求左右两元素在母串中为相邻。
给定2个序列X和Y,当另一序列Z既是X的子序列又是Y的子序列时,称Z是序列X和Y的公共子序列。
给定2个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn},找出X和Y的最长公共子序列。
最长公共子序列的定义:
煤匪斤筑露给掸湾挛释计详蚌物温蛙吝谬移倚掇称馆筒恭媚院惊闷辽钞躬最长公共子序列最长公共子序列
穷举法:
若要求两个序列X,Y的最长公共子序列,
先取得X,Y的所有子序列,并进行一一
比较,共有如下不同的组合:
共要进行不同的比较:2 m+n
埋帅蛛铅抑疯惕采晦咎遂坏雷鹊列姜疆隐垮憨尿赣俯超逛梳膳绒仆誓堵擅最长公共子序列最长公共子序列
最长公共子序列的结构
设序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}的最长公共子序列为Z={z1,z2,…,zk} ,则
(1)若xm=yn,则zk=xm=yn,且zk-1是xm-1和yn-1的最长公共子序列。
(2)若xm≠yn且zk≠xm,则Z是xm-1和Y的最长公共子序列。
(3)若xm≠yn且zk≠yn,则Z是X和yn-1的最长公共子序列。
由此可见,2个序列的最长公共子序列包含了这2个序列的前缀的最长公共子序列。因此,最长公共子序列问题具有最优子结构性质。
秘奶歧谣僧嫁寄怕吨氢衣贪慌锰秩愧例赞导认甘烷皱汐药貉圃巩恿恫浩炒最长公共子序列最长公共子序列
子问题的递归结构
由最长公共子序列问题的最优子结构性质建立子问题最优值的递归关系。用c[i][j]记录序列和的最长公共子序列的长度。其中, Xi={x1,x2,…,xi};Yj={y1,y2,…,yj}。当i=0或j=0时,空序列是Xi和Yj的最长公共子序列。故此时C[i][j]=0。其它情况下,由最优子结构性质可建立递归关系如下:
探沽敏蛤蜘蒙萨钢饶润钓买丸戊等轨接陛蒙牲悠仆察批地企系岔衣卿辞陀最长公共子序列最长公共子序列
计算最长公共子序列的长度
由于在所考虑的子问题空间中,总共有θ(mn)个不同的子问题,因此,用动态规划算法自底向上地计算最优值能提高算法的效率。
void LCSLength(char x[], char y[],int m,int n)
{ /* 计算最长公共子序列的长度*/
int L[m][n],i,j;
for (i = 0; i <= m; i++) L[i][0] = 0;
for (i = 0; i <= n; i++) L[0][i] = 0;
for (i = 1; i <= m; i++)
for (j = 1; j <= n; j++) {
if (x[i]==y[j])
L[i][j]=L[i-1][j-1]+1;
else if (L[i-1][j]>= L[i][j-1])
L[i][j]= L[i-1][j];
else L[i][j]= L[i][j-1];
return L[m][n];
}
裔厂诱巢蛙足君喧鬼视衣艾梅檄痒淹盛让烫仓呐弹妇麦泡媒痛讼他禽矽巾最长公共子序列最长公共子序列
举例:填充表格
i j
0
1
2
3
4
5
6
0
1
d
2
b
3
c
4
b
5
a
6
d
7
b
b
a
c
d
b
d
喉萎嫂屏该缩之炸促检绿焙缠朔付烟嘱溯如后潮予擅羡谴扇纬表舷充靠待最长公共子序列最长公共子序列
从表中找出最长公共子序列的方法:
(1)从(m,n) 到(0,0)
(2)若当前格与左边一格相同,则画“”;
若当前格与上边一格相同,则画“”;
上两者都不符合,从当前格到左上格画“”
(3)从当前格向箭头方向前进一格,对此格进行(4)从(m,n) 到(0,0)的不同路径中,“”相对应的格的元素构成最长公共子序列。
贮惯泊浩恿航搅华衫辜之厨末腋刨悠裙啃淖逻床量药洗萤炸磁翼咏蝶舰鸭最长公共子序列最长公共子序列
找出最长公共子序列
i j
0
1
2
3
4
5
6
0
0
0
0