longest-common-subsequence.md (1546B)
1 +++ 2 title = "Longest common subsequence" 3 +++ 4 5 # Longest common subsequence 6 7 Problem: 8 "Find LCS of <N,I,A,C,U,E> and <N,I,C,E,A,C>." 9 10 Solution: 11 Set up a table (2D array): 12 13 | j \ i | 0 | N | I | A | C | U | E | 14 | --- | --- | --- | --- | --- | --- | --- | --- | 15 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 16 | N | 0 | | | | | | | 17 | I | 0 | | | | | | | 18 | C | 0 | | | | | | | 19 | E | 0 | | | | | | | 20 | A | 0 | | | | | | | 21 | C | 0 | | | | | | | 22 23 Then, for every cell: 24 25 - If letter in row & column is the same, take the number diagonally up to the left and add 1. Place the result in the cell, draw an arrow pointing the cell that’s diagonally up and to the left — A[i-1, j-1] 26 - If not, compare neighbour to left and above, take the larger number and place it in the cell. Draw an arrow pointing left or up, depending on which number was used — A[i-1, j] or A[i, j-1] 27 28 The LCS length is the lowest rightmost cell. To find which elements are included in the subsequence, follow the arrows and record every cell that has a diagonal arrow pointing from it (it will be in reverse): 29 30  31 32 LCS = 4 — [N, I, A, C] 33 34 Worst-case complexity: O(m × n) 35 36 Extending: 37 38 To turn this into longest common increasing subsequence, create an array of elements from minimum to maximum, and then find LCS between this array and the input.