Longest Common Subsequence Problem Stepl: Analyzing the problem I Given two sequences aA brute-force method: [Naive X=<x1,X2,X3…x a How many subsequences for string x? Y=y1y2,y3-…yn a Check each one is also a subsequence of Find the longest common subsequence, where stringy a common subsequence of two strings is a Complexity other string y such that it is a subsequence of both of the two given strings Theorem 15.1 Optimal substructure of an Proof of Theorem 15 ■Letx=<x1x2…xm3,Y=sy1y2…yn> be two ■ Proof of"tfxn° yn then zk=xm° yn and zk1isan sequences and let Z=<z1, Z2,.,Zk? be a LCS LCS ofx and of x and y xm n, then z xm yn and zk-1 common subsequence of X andY, hich is a contradiction hence we have Xm-, and Yn-1 ZXm n and then, kxm implies that Z, is ar m Z,, is a common subsequence of Xm, andY m If xm -yo then zk -y, and zk is an LCS of Xn If not, there are another common subsequence andY which is longer than Zk, and then we append 清华太学未证想 Continuing proof of Theorem 15.1 Step 2: A recursive solution a Proof of"If xm l=yn, then(zk l=xm implies that a Let C[i,j be the length of the LCS of X, and Y, then Zk is an LCS of Xm-1 and Yy) a If z is not an LCS of Xm, and,, then it will conclude a contradiction that z is an lcs of x i,j=0 c={41-1,-]+ Mi=y max(cl,j-1, ci-1,j x*y3 清华大学 宋斌恒 13 Longest Common Subsequence Problem n Given two sequences n X=<x1 , x 2 , x 3 ,… ,xm> n Y=<y 1 , y 2 , y 3 ,… ,yn> n Find the longest common subsequence, where a common subsequence of two strings is another string y such that it is a subsequence of both of the two given strings. 清华大学 宋斌恒 14 Step1: Analyzing the problem n A brute-force method: [Naïve] n How many subsequences for string x? n Check each one is also a subsequence of string y. n Complexity? 清华大学 宋斌恒 15 Theorem 15.1 Optimal substructure of an LCS n Let X=<x1 ,x2 ,… ,xm> ,Y=<y1 ,y2 ,… ,yn> be two sequences and let Z=<z1 ,z2 ,… ,z k> be a LCS of X and Y. n If xm=yn , then zk=xm=yn and Zk-1 is an LCS of Xm-1 and Yn-1 n If xm !=yn , then zk != xm implies that Zk is an LCS of Xm-1 and Yn n If xm != yn , then zk != yn and Zk is an LCS of Xm and Yn-1 清华大学 宋斌恒 16 Proof of Theorem 15.1 n Proof of “If xm=yn , then zk=xm=yn and Zk-1 is an LCS of Xm-1 and Yn-1” n If zk !=xm ‡we could append xm to Z to obtain a longer common subsequence of X and Y, which is a contradiction, hence we have zk=xm=yn and n Zk-1 is a common subsequence of Xm-1 and Yn-1 , which we will show it is an LCS of Xm-1 and Yn-1 . If not, there are another common subsequence which is longer than Zk-1 and then we append yn to it, which is a contradiction. 清华大学 宋斌恒 17 Continuing proof of Theorem 15.1 n Proof of “If xm !=yn , then (zk != xm implies that Zk is an LCS of Xm-1 and Yn )” n If Zk is not an LCS of Xm-1 and Yn , then it will conclude a contradiction that Z is an LCS of X and Y. 清华大学 宋斌恒 18 Step 2: A recursive solution n Let C[i,j] be the length of the LCS of Xi and Yj , then ï î ï í ì - - ¹ - - + = = = i j i j c i j c i j x y c i j x y i j c i j max{ [ , 1], [ 1, ]} [ 1, 1] 1 0 , 0 [ , ]