最长公共子序列.ppt

最长公共子序列： 应用：打字比赛（规则，中外区别） SARS病毒 文件比较等等 两个一维事物的比较 定义：与子串的区别 算法：穷举法，动态规划法 代码实现：用C 穷举法: 若要求两个序列X，Y的最长公共子序列， 先取得X，Y的所有子序列，并进行一一 比较，共有如下不同的组合： 共要进行不同的比较：2 m+n 举例：填充表格 从表中找出最长公共子序列的方法： （1）从(m,n) 到 (0,0) （2）若当前格与左边一格相同，则画“ ”; 若当前格与上边一格相同，则画“ ”; 上两者都不符合，从当前格到左上格画“ ” （3）从当前格向箭头方向前进一格，对此格进行（4）从(m,n) 到 (0,0)的不同路径中，“ ”相对应的格的元素构成最长公共子序列。 找出最长公共子序列 求最长公共子序列 void LCS(char a[],int L[][],int m,int n) { /* 求最长公共子序列 */ int i,j,k; char c[m]; i=m;j=n;k=m; do { if(L[i][j]==L[i-1][j]) i--; else if(L[i][j]==L[i]j-1]) j--; else { c[k]=a[ii]; k--;i--;j--;} }while(i0j0); printf(“%s”,c+k+1); } 时间复杂度为：m+n=O(n) * * 辱倒料肖洞果泰府棘胶州巍嫉景酥疹器弃睹边计裔睬廖烃痞堕贮赚斩递沮最长公共子序列最长公共子序列 熟蔽袖考型什盗麓绒掩莫费呆胀短转参器武秉试兢蝎拜抡唁物闹纫盔霄德最长公共子序列最长公共子序列 若给定序列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={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