3 namespace Caxy\HtmlDiff;
5 use Caxy\HtmlDiff\Strategy\EqualMatchStrategy;
6 use Caxy\HtmlDiff\Strategy\MatchStrategyInterface;
11 * @var MatchStrategyInterface
13 protected $matchStrategy;
16 * LcsService constructor.
18 * @param MatchStrategyInterface $matchStrategy
20 public function __construct(MatchStrategyInterface $matchStrategy = null)
22 if (null === $matchStrategy) {
23 $matchStrategy = new EqualMatchStrategy();
26 $this->matchStrategy = $matchStrategy;
35 public function longestCommonSubsequence(array $a, array $b)
42 for ($i = 0; $i <= $m; $i++) {
46 for ($j = 0; $j <= $n; $j++) {
50 for ($i = 1; $i <= $m; $i++) {
51 for ($j = 1; $j <= $n; $j++) {
52 if ($this->matchStrategy->isMatch($a[$i - 1], $b[$j - 1])) {
53 $c[$i][$j] = 1 + (isset($c[$i - 1][$j - 1]) ? $c[$i - 1][$j - 1] : 0);
56 isset($c[$i][$j - 1]) ? $c[$i][$j - 1] : 0,
57 isset($c[$i - 1][$j]) ? $c[$i - 1][$j] : 0
63 $lcs = array_pad(array(), $m + 1, 0);
64 $this->compileMatches($c, $a, $b, $m, $n, $lcs);
77 protected function compileMatches($c, $a, $b, $i, $j, &$matches)
79 if ($i > 0 && $j > 0 && $this->matchStrategy->isMatch($a[$i - 1], $b[$j - 1])) {
80 $this->compileMatches($c, $a, $b, $i - 1, $j - 1, $matches);
82 } elseif ($j > 0 && ($i === 0 || $c[$i][$j - 1] >= $c[$i - 1][$j])) {
83 $this->compileMatches($c, $a, $b, $i, $j - 1, $matches);
84 } elseif ($i > 0 && ($j === 0 || $c[$i][$j - 1] < $c[$i - 1][$j])) {
85 $this->compileMatches($c, $a, $b, $i - 1, $j, $matches);