# run backtracking on lcs-matrix
sub backtracking_lcs {
	my $refmatrix=shift;
	my $ref_xlst=shift;
	my $ref_ylst=shift;
	my @lcs;
	my $x=scalar @$ref_xlst -1; 
	my $y=scalar @$ref_ylst -1;
	while ($y>0 && $x>0) {
		my $actual_value=$refmatrix->[$x]->[$y];
		my $actual_x=$x;
		my $actual_y=$y;
		my $actual_direction;
		if (
			($refmatrix->[$x-1]->[$y-1] >= $refmatrix->[$x-1]->[$y]) &&
			($refmatrix->[$x-1]->[$y-1] >= $refmatrix->[$x]->[$y-1])
		) { # go left upper
			$x--; $y--;
			$actual_direction="ul";
			
		} elsif ($refmatrix->[$x-1]->[$y] >= $refmatrix->[$x]->[$y-1]) { # go left
			$x--;
			$actual_direction="l";
		} else { # go upper
			$y--;
			$actual_direction="u";
		}
		# check if value is changed, then push to @lcs
		if ($actual_value > $refmatrix->[$x]->[$y]) {
			# push @lcs, $actual_x;
			push @lcs, "(".$ref_xlst->[$actual_x].")";
		} else {
			if ($actual_direction eq "u") {
				push @lcs, "+(".$ref_ylst->[$actual_y].")";
			} elsif ($actual_direction eq "l") {
				push @lcs, "-(".$ref_xlst->[$actual_x].")";
			} else {
				push @lcs, "+(".$ref_ylst->[$actual_y].")";
				push @lcs, "-(".$ref_xlst->[$actual_x].")";
			}
		}
	}
	while ($y > 0) { # get last stuff of ylst
		push @lcs, "+(".$ref_ylst->[$y].")";
		$y--;
	}
	while ($x > 0) { # get last stuff of xlst
		push @lcs, "-(".$ref_xlst->[$x].")";
		$x--;
	}
	@lcs=reverse @lcs; # reverse because backtracking
	return \@lcs;
}

# print out lcs matrix
sub print_diff {
	my $ref_matrix=shift;
	my $ref_xlst=shift;
	my $ref_ylst=shift;	
	print "DIFF: '";
	foreach my $i (@{ backtracking_lcs($ref_matrix, $ref_xlst, $ref_ylst) }) {
		print $i;
	}
	print "'\n";
}