Longest Common Subsequence (lcs) D A subsequence of a sequence/string S is obtained by deleting zero or more symbols from S. For example, the following are some subsequences of"president": pred, sdn, predent. In other words, the letters of a subsequence ofs appear in order in S, but they are not required to be consecutive. n The longest common subsequence problem is to find a maximum length common subsequence between two sequences. Copyright@ 2007 Pearson Addison-Wesley. All rights reserved. A Levitin "Intoduction b the Design& Analysis of Algorithms, 2nd ed, Ch 8 8-10
Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2 nd ed., Ch. 8 8-10 Longest Common Subsequence (LCS) A subsequence of a sequence/string S is obtained by deleting zero or more symbols from S. For example, the following are some subsequences of “president”: pred, sdn, predent. In other words, the letters of a subsequence of S appear in order in S, but they are not required to be consecutive. The longest common subsequence problem is to find a maximum length common subsequence between two sequences
LCS For instance, Sequence 1: president Sequence 2: providence Its LCS is pride. president providence Copyright@ 2007 Pearson Addison-Wesley. All rights reserved. A Levitin "Intoduction b the Design& Analysis of Algorithms, 2nd ed, Ch 8 8-11
Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2 nd ed., Ch. 8 8-11 LCS For instance, Sequence 1: president Sequence 2: providence Its LCS is priden. president providence
LCS Another example Sequence 1: algorithm Sequence 2: alignment One of its lcs is algm. i t h m n m e n t Copyright@ 2007 Pearson Addison-Wesley. All rights reserved. A Levitin "Intoduction b the Design& Analysis of Algorithms, 2nd ed, Ch 8 8-12
Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2 nd ed., Ch. 8 8-12 LCS Another example: Sequence 1: algorithm Sequence 2: alignment One of its LCS is algm. a l g o r i t h m a l i g n m e n t
How to compute LCS? o LetA=a a2,,amand B=b.,bn o len(i,): the length of an LCS between n12 and b,b2…b o With proper initializationS, len(i,j can be computed as follows. if i=Oor j=0, len(i,j=len(i-1,j-1)+ if i,J>Oand a; =b max(len(i,j-1),len(i-1,))) if i,j>O and a;+ b Copyright@ 2007 Pearson Addison-Wesley. All rights reserved. A Levitin "Intoduction b the Design& Analysis of Algorithms, 2nd ed, Ch 8 8-13
Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2 nd ed., Ch. 8 8-13 How to compute LCS? Let A=a1a2…am and B=b1b2…bn . len(i, j): the length of an LCS between a1a2…ai and b1b2…bj With proper initializations, len(i, j) can be computed as follows. , max( ( , 1), ( 1, )) if , 0 and . ( 1, 1) 1 if , 0 and 0 if 0 or 0, ( , ) − − − − + = = = = i j i j len i j len i j i j a b len i j i j a b i j len i j
procedure LCs-Length(A, B 1. for i-0 to m dolen(, 0=0 2. forj<l to n dolen(0.)=0 3.fori← I to m do for I to n d if a, =b,then len(i,j)=len(i-1,j-1)+ prev(1,1)=K else if len(i-1,j)>len(i,j-1) len(i,j)=len(i-1,j) then prev(i,j)="个" len(i,j=len(i,j-l) else prev(i,j) 9. return len and prev Copyright@ 2007 Pearson Addison-Wesley. All rights reserved. A Levitin "Intoduction b the Design& Analysis of Algorithms, 2nd ed, Ch 8 8-14
Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2 nd ed., Ch. 8 8-14 procedure LCS-Length(A, B) 1. for i ← 0 to m dolen(i,0) = 0 2. for j ← 1 to n dolen(0,j) = 0 3. for i ← 1 to m do 4. for j ← 1 to n do 5. if i j a = b then = = − − + ( , ) " " ( , ) ( 1, 1) 1 prev i j len i j len i j 6. else if len(i −1, j) len(i, j −1) 7. then = = − ( , ) " " ( , ) ( 1, ) prev i j len i j len i j 8. else = = − ( , ) " " ( , ) ( , 1) prev i j len i j len i j 9. return len and prev