use strict;
use warnings;
#debug = 1 displays score and traceback matrix


my $debug = 0;
my $now = time;

print"Gib erste Sequenenz ein \n";
my $seq1=<STDIN>;

print"Gib  zweite Sequenz ein \n";
my $seq2=<STDIN>;

#################################################################################################### 
# 							Schema für Score													   #
####################################################################################################

my $MATCH    =  1; # +1 für Buchtstabe, der ein Match macht
my $MISMATCH = -1; # -1 für Buchstabe, der einen Mismatch macht
my $GAP      = -1; # -1 für Lücke
 
 
#################################################################################################### 
#                      Initialisierung / Programmstart	                                           #
####################################################################################################
my @matrix;
$matrix[0][0]{score}   = 0;
$matrix[0][0]{pointer} = "none";
for(my $j = 1; $j <= length($seq1); $j++) {
$matrix[0][$j]{score}   = $GAP * $j;
$matrix[0][$j]{pointer} = "left";
}
for (my $i = 1; $i <= length($seq2); $i++) {
$matrix[$i][0]{score}   = $GAP * $i;
$matrix[$i][0]{pointer} = "up";
}

####################################################################################################
# 									Auffüllen                                                      #
####################################################################################################
for(my $i = 1; $i <= length($seq2); $i++) {
for(my $j = 1; $j <= length($seq1); $j++) {
my ($diagonal_score, $left_score, $up_score);
 
 
####################################################################################################
#                            berechnet match score												   #
####################################################################################################
my $letter1 = substr($seq1, $j-1, 1);
my $letter2 = substr($seq2, $i-1, 1);
if ($letter1 eq $letter2) {
$diagonal_score = $matrix[$i-1][$j-1]{score} + $MATCH;
}
else {
$diagonal_score = $matrix[$i-1][$j-1]{score} + $MISMATCH;
}
 
 
####################################################################################################
#  							berechnet gap scores												   #
####################################################################################################
$up_score   = $matrix[$i-1][$j]{score} + $GAP;
$left_score = $matrix[$i][$j-1]{score} + $GAP;



#################################################################################################### 
#                             aussuchen des best score											   #
####################################################################################################
if ($diagonal_score >= $up_score) {
if ($diagonal_score >= $left_score) {
$matrix[$i][$j]{score}   = $diagonal_score;
$matrix[$i][$j]{pointer} = "diagonal";
}
else {
$matrix[$i][$j]{score}   = $left_score;
$matrix[$i][$j]{pointer} = "left";
}
} else {
if ($up_score >= $left_score) {
$matrix[$i][$j]{score}   = $up_score;
$matrix[$i][$j]{pointer} = "up";
}
else {
$matrix[$i][$j]{score}   = $left_score;
$matrix[$i][$j]{pointer} = "left";
}
}
}
}

##########################################################################################################
#									print matrix     													 #
########################################################################################################## 

my $j = length($seq1);
my $i = length($seq2);
my @seq1 = ("*");
my @seq2 = ("*");
my @s1=split(//,$seq1);
my @s2=split(//,$seq2);
push (@seq1,@s1);
push (@seq2,@s2);
if ($debug ==1 ) {

print "The Score Matrix\n";
print "-----------------------\n";
print "\t";
foreach (@seq1) {
print $_."\t";
}
print "\n";
for (my $u=0;$u<=$i;$u++) {
print $seq2[$u]."\t";
for (my $v=0;$v<=$j;$v++) {
print $matrix[$u][$v]{score}."\t";
}
print "\n";
}
 
#####################################################################################################
print "The Trace Matrix\n";
print "-----------------------\n";
print "\t";
foreach (@seq1) {
print $_."\t";
}
print "\n";
for (my $u=0;$u<=$i;$u++) {
print $seq2[$u]."\t";
for (my $v=0;$v<=$j;$v++) {
 
if ($matrix[$u][$v]{pointer} eq "none") {print  "N\t";}
if ($matrix[$u][$v]{pointer} eq "left") {print  "L\t";}
if ($matrix[$u][$v]{pointer} eq "up") {print  "U\t";}
if ($matrix[$u][$v]{pointer} eq "diagonal") {print  "D\t";}
 
}
print "\n";
}
 
}
my $align1 = "";
my $align2 = "";
 
my $score = $matrix[$i][$j]{score};
 
while (1) {
last if $matrix[$i][$j]{pointer} eq "none";
 
if ($matrix[$i][$j]{pointer} eq "diagonal") {
$align1 .= substr($seq1, $j-1, 1);
$align2 .= substr($seq2, $i-1, 1);
$i--; $j--;
}
elsif ($matrix[$i][$j]{pointer} eq "left") {
$align1 .= substr($seq1, $j-1, 1);
$align2 .= "-";
$j--;
}
elsif ($matrix[$i][$j]{pointer} eq "up") {
$align1 .= "-";
$align2 .= substr($seq2, $i-1, 1);
$i--;
}
}
 
$align1 = reverse $align1;
$align2 = reverse $align2;
 
print "Best Alignment\n";
print "--------------\n";
print "Seq1:\t$align1\n";
print "Seq2:\t$align2\n";
print "score = $score\n";
 
print time - $now." second\(s\)\n";