<p>The easiest way is to record all matches during the iteration through the matrix using the naive implementation.</p>

<p>I needed <code>allLCS()</code> for tests, if other algorithms provide a valid solution, which must be one of all possible LCS.</p>

<p>The code is on <a href="https://github.com/wollmers/LCS" rel="nofollow noreferrer">github</a>.</p>

<p>It's in Perl, but easy to understand. Iterate through the matrix and add the matches in the cells. At end the bottom right cell contains the length of the LCS. That's the naive algorithm. Now record at each match the coordinates as an array [i,j] in a hash with the match count as key. </p>

<pre class="lang-perl prettyprint-override"><code># get all LCS of two arrays
# records the matches by rank
sub allLCS {
  my ($self,$X,$Y) = @_;

  my $m = scalar @$X;
  my $n = scalar @$Y;

  my $ranks = {}; # e.g. '4' =&gt; [[3,6],[4,5]]
  my $c = [];
  my ($i,$j);

  for (0..$m) {$c-&gt;[$_][0]=0;}
  for (0..$n) {$c-&gt;[0][$_]=0;}
  for ($i=1;$i&lt;=$m;$i++) {
    for ($j=1;$j&lt;=$n;$j++) {
      if ($X-&gt;[$i-1] eq $Y-&gt;[$j-1]) {
        $c-&gt;[$i][$j] = $c-&gt;[$i-1][$j-1]+1;
        push @{$ranks-&gt;{$c-&gt;[$i][$j]}},[$i-1,$j-1];
      }
      else {
        $c-&gt;[$i][$j] =
          ($c-&gt;[$i][$j-1] &gt; $c-&gt;[$i-1][$j])
            ? $c-&gt;[$i][$j-1]
            : $c-&gt;[$i-1][$j];
      }
    }
  }
  my $max = scalar keys %$ranks;
  return $self-&gt;_all_lcs($ranks,1,$max);
} 

</code></pre>

<p>At the end this collection of recorded matches is connected by the method <code>_all_lcs()</code>:</p>

<pre class="lang-perl prettyprint-override"><code>sub _all_lcs {
  my ($self,$ranks,$rank,$max) = @_;

  my $R = [[]];

  while ($rank &lt;= $max) {
    my @temp;
    for my $path (@$R) {
      for my $hunk (@{$ranks-&gt;{$rank}}) {
        if (scalar @{$path} == 0) {
          push @temp,[$hunk];
        }
        elsif (($path-&gt;[-1][0] &lt; $hunk-&gt;[0]) &amp;&amp; ($path-&gt;[-1][1] &lt; $hunk-&gt;[1])) {
          push @temp,[@$path,$hunk];
        }
      }
    }
    @$R = @temp;
    $rank++;
  }
  return $R;
}
</code></pre>

<p>The code is inspired by the paper</p>

<p>Ronald I. Greenberg. <a href="https://arxiv.org/pdf/cs/0211001.pdf" rel="nofollow noreferrer">Fast and Simple Computation of All Longest Common Subsequences</a></p>
LCS algorithm: How to find out from a Table, how many longest common subsequences are found?
<p>I implement the Longest Common Subsequence problem in C#. I need to detect <strong>ALL the common maximal subsequences</strong> between two strings.</p>

<p>To do this, I create a table using <a href="https://en.wikipedia.org/wiki/Hirschberg%27s_algorithm" rel="nofollow noreferrer">Needleman-Wunsch algorithm</a> to store the LCS sequence for each step of the calculation. </p>

<p>Is there any chance to determine, <strong><em>how many</em></strong> maximal subsequences were found (using a table)?</p>

<p>Depending on this I want to choose a method how to collect each subsequence. The point is, for <em>one subsequence</em> recursion is not required, so it will give a <em>better performance</em>. And its crucial for my task.</p>

<p>Here is a code snippet, where the basic functions from the project are implemented:</p>

<pre><code>    private static int[][] GetMatrixLCS(string x, string y)
        {
            var lenX = x.Length;
            var lenY = y.Length;
            matrixLCS = new int[lenX + 1][];
            for (var i = 0; i &lt; matrixLCS.Length; i++)
            {
                matrixLCS[i] = new int[lenY + 1];
            }
            for (int i = 0; i &lt;= lenX; i++)
            {
                for (int j = 0; j &lt;= lenY; j++)
                {
                    if (i == 0 || j == 0)
                        matrixLCS[i][j] = 0;
                    else
                    if (x[i - 1] == y[j - 1])
                        matrixLCS[i][j] = matrixLCS[i - 1][j - 1] + 1;
                    else
                        matrixLCS[i][j] = Math.Max(matrixLCS[i - 1][j], matrixLCS[i][j - 1]);
                }
            }
            return matrixLCS;
        }

    static HashSet&lt;string&gt; FindAllLcs(string X, string Y, int lenX, int lenY)
        {
            var set = new HashSet&lt;string&gt;();
            if (lenX == 0 || lenY == 0)
                return emptySet;
            if (X[lenX - 1] == Y[lenY - 1])
            {
                var tempResult = FindAllLcs(X, Y, lenX - 1, lenY - 1);
                foreach (var temp in tempResult)
                    set.Add(temp + X[lenX - 1]);
                return set;
            }
            if (matrixLCS[lenX - 1][lenY] &gt;= matrixLCS[lenX][lenY - 1])
                set = FindAllLcs(X, Y, lenX - 1, lenY);
            if (matrixLCS[lenX][lenY - 1] &gt;= matrixLCS[lenX - 1][lenY])
                set.UnionWith(FindAllLcs(X, Y, lenX, lenY - 1));
            return set;
        }
</code></pre>

<p>And the example with two types of inputs and expected outputs:</p>

<pre><code>    public void SingleOutput()
    {
    var sequence = LCS.FindLCS("ABC", "AB");
    Assert.AreEqual(1, sequence.Length);
    Assert.AreEqual("AB", sequence[0]);
    }

    public void MultipleOutput() 
    { 
    var sequence = LCS.FindLCS("BCAB", "ABC"); 
    Assert.AreEqual(2, sequence.Length); 
    Assert.AreEqual("AB", sequence [0]);
    Assert.AreEqual("BC", sequence [1]);
    }
</code></pre>

<p>Any help would be strongly appreciated.</p>