title: longest common subsequence print all subsequences
body: <p>how to display all the substrings of a longest common substring of two substring
  i know the dp method to calculate length of lcs
  but how to display all those lcs
  code for lcs</p>
  
  <pre><code>       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]
  </code></pre>
  
  <p>i couldnt find a good article on net for how to find all lcs</p>
  
  <p>string 1=abcabcaa
  string 2=acbacba</p>
  
  <p>all lcs</p>
  
  <p>ababa
  abaca
  abcba
  acaba
  acaca
  acbaa
  acbca</p>
  
  <p>i already know the dp method to calculate lcs
  any help would be appreciated</p>
  
  <p>i found this on wiki</p>
  
  <pre><code>             function backtrackAll(C[0..m,0..n], X[1..m], Y[1..n], i, j)
    if i = 0 or j = 0
      return {""}
      else if X[i] = Y[j]
      return {Z + X[i] for all Z in backtrackAll(C, X, Y, i-1, j-1)}
     else
      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
  </code></pre>
  
  <p>but am having diificulty in understanding it</p>