matchStrategy = $matchStrategy;
}
/**
* @param array $a
* @param array $b
*
* @return array
*/
public function longestCommonSubsequence(array $a, array $b)
{
$c = array();
$m = count($a);
$n = count($b);
for ($i = 0; $i <= $m; $i++) {
$c[$i][0] = 0;
}
for ($j = 0; $j <= $n; $j++) {
$c[0][$j] = 0;
}
for ($i = 1; $i <= $m; $i++) {
for ($j = 1; $j <= $n; $j++) {
if ($this->matchStrategy->isMatch($a[$i - 1], $b[$j - 1])) {
$c[$i][$j] = 1 + (isset($c[$i - 1][$j - 1]) ? $c[$i - 1][$j - 1] : 0);
} else {
$c[$i][$j] = max(
isset($c[$i][$j - 1]) ? $c[$i][$j - 1] : 0,
isset($c[$i - 1][$j]) ? $c[$i - 1][$j] : 0
);
}
}
}
$lcs = array_pad(array(), $m + 1, 0);
$this->compileMatches($c, $a, $b, $m, $n, $lcs);
return $lcs;
}
/**
* @param $c
* @param $a
* @param $b
* @param $i
* @param $j
* @param $matches
*/
protected function compileMatches($c, $a, $b, $i, $j, &$matches)
{
if ($i > 0 && $j > 0 && $this->matchStrategy->isMatch($a[$i - 1], $b[$j - 1])) {
$this->compileMatches($c, $a, $b, $i - 1, $j - 1, $matches);
$matches[$i] = $j;
} elseif ($j > 0 && ($i === 0 || $c[$i][$j - 1] >= $c[$i - 1][$j])) {
$this->compileMatches($c, $a, $b, $i, $j - 1, $matches);
} elseif ($i > 0 && ($j === 0 || $c[$i][$j - 1] < $c[$i - 1][$j])) {
$this->compileMatches($c, $a, $b, $i - 1, $j, $matches);
}
}
}