2最长公共子序列

1、最长公共子序列,子串比较与概率算法,两个一维事物比较：,相似 ： LCS算法 比较 完全相等： 一一对应，概率算法 等 相等 部分相等 ：模式匹配-KMP算法,最长公共子序列：,应用：打字比赛（规则，中外区别） 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、串则要求左右两元素在母串中为相邻。 给定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

3、)若xmyn且zkxm，则Z是xm-1和Y的最长公共子序列。 (3)若xmyn且zkyn，则Z是X和yn-1的最长公共子序列。,由此可见，2个序列的最长公共子序列包含了这2个序列的前缀的最长公共子序列。因此，最长公共子序列问题具有最优子结构性质。,子问题的递归结构,由最长公共子序列问题的最优子结构性质建立子问题最优值的递归关系。用cij记录序列和的最长公共子序列的长度。其中， Xi=x1,x2,xi；Yj=y1,y2,yj。当i=0或j=0时，空序列是Xi和Yj的最长公共子序列。故此时Cij=0。其它情况下，由最优子结构性质可建立递归关系如下：,计算最长公共子序列的长度,由于在所考虑的子问题空

4、间中，总共有(mn)个不同的子问题，因此，用动态规划算法自底向上地计算最优值能提高算法的效率。,void LCSLength(char x, char y,int m，int n) /* 计算最长公共子序列的长度 */ int Lmn,i，j; for (i = 0; i = Lij-1) Lij= Li-1j; else Lij= Lij-1; return Lmn; ,举例：填充表格,从表中找出最长公共子序列的方法：,（1）从(m,n) 到 (0,0) （2）若当前格与左边一格相同，则画“ ”; 若当前格与上边一格相同，则画“ ”; 上两者都不符合，从当前格到左上格画“ ” （3）从当前格

5、向箭头方向前进一格，对此格进行（2） （4）从(m,n) 到 (0,0)的不同路径中，“ ”相对应的格的元素构成最长公共子序列。,找出最长公共子序列,（bcbd,bcdb,badb）,求最长公共子序列,void LCS(char a,int L,int m,int n) /* 求最长公共子序列 */ int i,j,k; char cm; i=m;j=n;k=m; do if(Lij=Li-1j) i-; else if(Lij=Lij-1) j-; else ck=aii; k-;i-;j-; while(i0 时间复杂度为：m+n=O(n),算法的改进,如果只需要计算最长公共子序列的长度，

6、则算法的空间需求可大大减少。事实上，在计算cij时，只用到数组c的第i行和第i-1行。因此，用2行的数组空间就可以计算出最长公共子序列的长度。进一步的分析还可将空间需求减至O(min(m,n)。 思考题：如何对程序进行改正，作为思考题。,子串比较：,G等搜索工具的目的是从信息海洋中进行串匹配查找。 最著名的子串匹配算法是KMP算法。 KMP算法利用关键词内部的相似特点，节省了时间复杂度：O（m+n),概率算法：,我们重点学习概率算法，概率算法是非确定性算法，即每一步是随机的。 经典问题1：生日问题 有多少人在一起使得其中至少有两个人生日相同的机会超过没有人生日相同的机会。即有相同生日的机会概率超过1/2. 经典问题2：圆周率的计算 祖冲之等，国外有投针法。,素数的概率判定算法,判定所给自然数n是否是素数？ 意义：密码学，计算机测试等 素数特点：分布稀疏 10 4 共有1229个。 10 8 共有5761455个。 设(x)为小于或等于x的全部素数个数，则 即： (x) x/ln x,定理(Wilson):,(Wilson): n是素数的充要条件是：