Longest common subsequence for PHP using arrays

LCSTest.php

<?php

class LCSTest extends PHPUnit_Framework_TestCase
{
  /**
   * Returns the longest common subsequence of two arrays.
   * 
   *   @link http://en.wikipedia.org/wiki/Longest_common_subsequence_problem
   *
   * @param  array $left   The first array.
   * @param  array $right  The second array.
   * 
   * @return array         The longest common subsequence.
   */
  public function longestCommonSubsequence(array $left, array $right)
  {
    $m = count($left);
    $n = count($right);

    // $a[$i][$j] = length of LCS of $left[$i..$m] and $right[$j..$n]
    $a = array();

    // compute length of LCS and all subproblems via dynamic programming
    for ($i = $m - 1; $i >= 0; $i--)
    {
      for ($j = $n - 1; $j >= 0; $j--)
      {
        if ($left[$i] == $right[$j])
        {
          $a[$i][$j] = (isset($a[$i + 1][$j + 1]) ? $a[$i + 1][$j + 1] : 0) + 1;
        }
        else
        {
          $a[$i][$j] = max(
            (isset($a[$i + 1][$j]) ? $a[$i + 1][$j] : 0)
            , (isset($a[$i][$j + 1]) ? $a[$i][$j + 1] : 0)
          );
        }
      }
    }

    // recover LCS itself
    $i = 0;
    $j = 0;
    $lcs = array();

    while($i < $m && $j < $n)
    {
      if ($left[$i] == $right[$j])
      {
        $lcs[] = $left[$i];

        $i++;
        $j++;
      }
      elseif (
        (isset($a[$i + 1][$j]) ? $a[$i + 1][$j] : 0)
        >= (isset($a[$i][$j + 1]) ? $a[$i][$j + 1] : 0)
      ) {
        $i++;
      }
      else
      {
        $j++;
      }
    }

    return $lcs;
  }
  
  /**
   * @return array
   */
  public function longestCommonSubsequenceData()
  {
    $data = array();

    $left = array('A', 'B', 'C');
    $right = array('A', 'B', 'C');
    $expected = array('A', 'B', 'C');
    $data[] = array($left, $right, $expected);

    $left = array('A', 'B', 'C', 'D', 'E', 'F');
    $right = array('B', 'C', 'D', 'E');
    $expected = array('B', 'C', 'D', 'E');
    $data[] = array($left, $right, $expected);

    $left = array('A', 'B', 'D', 'E');
    $right = array('A', 'C', 'D', 'F');
    $expected = array('A', 'D',);
    $data[] = array($left, $right, $expected);

    $left = array('A', 'B', 'C', 'D', 'E', 'F');
    $right = array('J', 'A', 'D', 'F', 'A', 'F', 'K', 'D', 'F', 'B', 'C', 'D', 'E', 'H', 'J', 'D', 'F', 'G');
    $expected = array('A', 'B', 'C', 'D', 'E', 'F');
    $data[] = array($left, $right, $expected);

    $left = array('A', 'B', 'C', 'D', 'E', 'F');
    $right = array('A');
    $expected = array('A');
    $data[] = array($left, $right, $expected);

    $left = array('A', 'B', 'C', 'D', 'E', 'F');
    $right = array('D');
    $expected = array('D');
    $data[] = array($left, $right, $expected);

    $left = array('A', 'B', 'C', 'D', 'E', 'F');
    $right = array('F');
    $expected = array('F');
    $data[] = array($left, $right, $expected);

    $left = array('J', 'A', 'F', 'A', 'F', 'K', 'D', 'B', 'C', 'E', 'H', 'J', 'D', 'F');
    $right = array('J', 'D', 'F', 'A', 'K', 'D', 'F', 'C', 'D', 'E', 'J', 'D', 'F', 'G');
    $expected = array('J', 'F', 'A', 'K', 'D', 'C', 'E', 'J', 'D', 'F');
    $data[] = array($left, $right, $expected);

    $left = array('A', 'B', 'C');
    $right = array('D', 'E', 'F');
    $expected = array();
    $data[] = array($left, $right, $expected);

    return $data;
  }
	
  /**
   * @dataProvider longestCommonSubsequenceData
   */
  public function testLongestCommonSubsequence($left, $right, $expected)
  {
    $this->assertEquals($expected, $this->longestCommonSubsequence($left, $right));
    $this->assertEquals($expected, $this->longestCommonSubsequence($right, $left));
  }
}