Editing Longest common subsequence (section)

== Code for the dynamic programming solution ==
{{unreferenced section|date=March 2013}}

=== Computing the length of the LCS ===
The function below takes as input sequences <code>X[1..m]</code> and <code>Y[1..n]</code>, computes the LCS between <code>X[1..i]</code> and <code>Y[1..j]</code> for all <code>1 ≤ i ≤ m</code> and <code>1 ≤ j ≤ n</code>, and stores it in <code>C[i,j]</code>. <code>C[m,n]</code> will contain the length of the LCS of <code>X</code> and <code>Y</code>.<ref name=":1">{{Introduction to Algorithms|3 |chapter=Dynamic Programming |pages=394}}</ref>

 '''function''' LCSLength(X[1..m], Y[1..n])
     C = array(0..m, 0..n)
     '''for''' i := 0..m
         C[i,0] = 0
     '''for''' j := 0..n
         C[0,j] = 0
     '''for''' i := 1..m
         '''for''' j := 1..n
             '''if''' X[i] = Y[j]
                 C[i,j] := C[i-1,j-1] + 1
             '''else'''
                 C[i,j] := max(C[i,j-1], C[i-1,j])
     '''return''' C[m,n]

Alternatively, [[memoization]] could be used.

=== Reading out a LCS ===
The following function [[backtracking|backtracks]] the choices taken when computing the <code>C</code> table. If the last characters in the prefixes are equal, they must be in an LCS. If not, check what gave the largest LCS of keeping <math>x_i</math> and <math>y_j</math>, and make the same choice. Just choose one if they were equally long. Call the function with <code>i=m</code> and <code>j=n</code>.

 '''function''' backtrack(C[0..m,0..n], X[1..m], Y[1..n], i, j)
     '''if''' i = 0 '''or''' j = 0
         '''return''' ""
     '''if ''' X[i] = Y[j]
         '''return''' backtrack(C, X, Y, i-1, j-1) + X[i]
     '''if''' C[i,j-1] > C[i-1,j]
         '''return''' backtrack(C, X, Y, i, j-1)
     '''return''' backtrack(C, X, Y, i-1, j)

=== Reading out all LCSs ===
If choosing <math>x_i</math> and <math>y_j</math> would give an equally long result, read out both resulting subsequences. This is returned as a set by this function. Notice that this function is not polynomial, as it might branch in almost every step if the strings are similar.

 '''function''' backtrackAll(C[0..m,0..n], X[1..m], Y[1..n], i, j)
     '''if''' i = 0 '''or''' j = 0
         '''return''' {""}
     '''if''' X[i] = Y[j]
         '''return''' {Z + X[i] '''for all''' Z '''in''' backtrackAll(C, X, Y, i-1, j-1)}
     R := {}
     '''if''' C[i,j-1] ≥ C[i-1,j]
         R := backtrackAll(C, X, Y, i, j-1)
     '''if''' C[i-1,j] ≥ C[i,j-1]
         R := R ∪ backtrackAll(C, X, Y, i-1, j)
     '''return''' R

=== Print the diff ===
This function will backtrack through the C matrix, and print the [[diff]] between the two sequences. Notice that you will get a different answer if you exchange <code>≥</code> and <code>&lt;</code>, with <code>&gt;</code> and <code>≤</code> below.

 '''function''' printDiff(C[0..m,0..n], X[1..m], Y[1..n], i, j)
     '''if''' i >= 0 '''and''' j >= 0 '''and''' X[i] = Y[j]
         printDiff(C, X, Y, i-1, j-1)
         print "  " + X[i]
     '''else if''' j > 0 '''and''' (i = 0 '''or''' C[i,j-1] ≥ C[i-1,j])
         printDiff(C, X, Y, i, j-1)
         print "+ " + Y[j]
     '''else if''' i > 0 '''and''' (j = 0 '''or''' C[i,j-1] < C[i-1,j])
         printDiff(C, X, Y, i-1, j)
         print "- " + X[i]
     '''else'''
         print ""

=== Example ===
Let <math>X</math> be “<code>XMJYAUZ</code>” and <math>Y</math> be “<code>MZJAWXU</code>”. The longest common subsequence between <math>X</math> and <math>Y</math> is “<code>MJAU</code>”. The table <code>C</code> shown below, which is generated by the function <code>LCSLength</code>, shows the lengths of the longest common subsequences between prefixes of <math>X</math> and <math>Y</math>. The <math>i</math>th row and <math>j</math>th column shows the length of the LCS between <math>X_{1..i}</math> and <math>Y_{1..j}</math>.

{| class="wikitable" style="text-align: center;"
|-
! colspan="2" rowspan="2" |
! 0 !! 1 !! 2 !! 3 !! 4 !! 5 !! 6 !! 7
|-
! ε !! M !! Z !! J !! A !! W !! X !! U
|-
! 0 !! ε
| style="background:yellow" | '''0''' || 0 || 0 || 0 || 0 || 0 || 0 || 0
|-
! 1 !! X
| style="background:yellow" | 0 || 0 || 0 || 0 || 0 || 0 || 1 || 1
|-
! 2 !! M
| 0 || style="background:yellow" | '''1''' || style="background:yellow" | 1 || 1 || 1 || 1 || 1 || 1
|-
! 3 !! J
| 0 || 1 || 1 || style="background:yellow" | '''2''' || 2 || 2 || 2 || 2
|-
! 4 !! Y
| 0 || 1 || 1 || style="background:yellow" | 2 || 2 || 2 || 2 || 2
|-
! 5 !! A
| 0 || 1 || 1 || 2 || style="background:yellow" | '''3''' || style="background:yellow" | 3 || style="background:yellow" | 3 || 3
|-
! 6 !! U
| 0 || 1 || 1 || 2 || 3 || 3 || 3 || style="background:yellow" | '''4'''
|-
! 7 !! Z
| 0 || 1 || 2 || 2 || 3 || 3 || 3 || style="background: yellow" | 4
|}

The <span style="background: yellow">highlighted</span> numbers show the path the function <code>backtrack</code> would follow from the bottom right to the top left corner, when reading out an LCS. If the current symbols in <math>X</math> and <math>Y</math> are equal, they are part of the LCS, and we go both up and left (shown in '''bold'''). If not, we go up or left, depending on which cell has a higher number. This corresponds to either taking the LCS between <math>X_{1..i-1}</math> and <math>Y_{1..j}</math>, or <math>X_{1..i}</math> and <math>Y_{1..j-1}</math>.