# 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;
		if (
			($refmatrix->[$x-1]->[$y-1] >= $refmatrix->[$x-1]->[$y]) &&
			($refmatrix->[$x-1]->[$y-1] >= $refmatrix->[$x]->[$y-1])
		) { # go left upper
			$x--; $y--;
		} elsif ($refmatrix->[$x-1]->[$y] >= $refmatrix->[$x]->[$y-1]) { # go left
			$x--;
		} else { # go upper
			$y--;
		}
		# check if value is changed, then push to @lcs
		if ($actual_value > $refmatrix->[$x]->[$y]) {
			push @lcs, $actual_x;
		}
	}
	@lcs=reverse @lcs; # reverse because backtracking
	return \@lcs;
}			

# print out lcs matrix
sub print_lcs {
	my $ref_matrix=shift;
	my $ref_xlst=shift;
	my $ref_ylst=shift;	
	print "LCS: '";
	foreach my $i (@{ backtracking_lcs($ref_matrix, $ref_xlst, $ref_ylst) }) {
		print $ref_xlst->[$i];
	}
	print "'\n";
}