Diff::longestCommonSubsequence

protected function longestCommonSubsequence(array $a, $lowerA, $upperA, array $b, $lowerB, $upperB)
{
	// Skipping equal lines at the start
	while ($lowerA < $upperA && $lowerB < $upperB && $a[$lowerA] == $b[$lowerB])
	{
		$lowerA++;
		$lowerB++;
	}

	// Skipping equal lines at the end
	while ($lowerA < $upperA && $lowerB < $upperB && $a[$upperA - 1] == $b[$upperB - 1])
	{
		$upperA--;
		$upperB--;
	}

	if ($lowerA === $upperA)
	{
		// mark as inserted lines.
		while ($lowerB < $upperB)
		{
			$this->modifiedB[$lowerB++] = true;
		}
	}
	else
	{
		if ($lowerB === $upperB)
		{
			// mark as deleted lines.
			while ($lowerA < $upperA)
			{
				$this->modifiedA[$lowerA++] = true;
			}
		}
		else
		{
			// Find the middle snake and length of an optimal path for A and B
			$sms = $this->shortestMiddleSnake($a, $lowerA, $upperA, $b, $lowerB, $upperB);

			// The path is from LowerX to (x,y) and (x,y) to UpperX
			$this->longestCommonSubsequence($a, $lowerA, $sms['x'], $b, $lowerB, $sms['y']);
			$this->longestCommonSubsequence($a, $sms['x'], $upperA, $b, $sms['y'], $upperB);
		}
	}
}