Towards a better algorithm Simplification 1. Look at the length of a longest-common subsequence 2. Extend the algorithm to find the lcs itself. Notation: Denote the length of a sequence s Strategy: Consider prefixes of x and y Define ci,j=LCs([1.i,yll.i Then, cm, n]=LCS(x, y) c 2001 by Charles E Leiserson Introduction to Agorithms Day 26 L15.4© 2001 by Charles E. Leiserson Introduction to Algorithms Day 26 L15.4 Towards a better algorithm Simplification: 1. Look at the length of a longest-common subsequence. 2. Extend the algorithm to find the LCS itself. Strategy: Consider prefixes of x and y. • Define c[i, j] = | LCS(x[1 . . i], y[1 . . j])|. • Then, c[m, n] = | LCS(x, y)|. Notation: Denote the length of a sequence s by |s|