Hi! I am new to Perl and very stuck.
I am trying to create a Perl implementation of the LCS algorithm en.wikipedia.org/wiki/Longest_common_subsequence_problem
I am required to do a comparison of two text files without the use of Text::Diff and I THINK(suggestions welcomed) this is how I should be go about it.
I am having trouble converting the pseudo code functions found in the link. This is what I have so far but have no idea if I am on the right track.
sub wikiLCSLength
{
#$file1 = $_[0];
#$file2 = $_[1];
#$file1 = "i b c d e f g h i";
#$file2 = "a b c d e f f f f";
@m = ("a", "b", "c", "d", "e");
@n = ("a", "b", "c", "e", "e");
$mLength = scalar @m;
$nLength = scalar @n;
#Initialize the multidimensional array
for(my $i = 0; $i<= $mLength; $i++)
{
for(my $j = 0; $j<= $nLength; $j++)
{
$C[$i][$j] = 0;
}
}
for($i = 0; $i <= $mLength; $i++)
{
$C[$i][0] = 0;
}
for($j = 0; $j <= $nLength; $j++)
{
$C[0][$j] = 0;
}
for($i=1; $i<$mLength; $i++)
{
for($j=1; $j<$nLength; $j++)
{
if($m[$i] eq $n[$j])
{
$C[$i][$j] = $C[$i-1][$j-1] + 1;
} else
{
$C[$i][$j] = max(($C[$i][$j-1]),($C[$i-1][$j]));
}
}
}
&wikiBacktrack(\@C, \@m, \@n, $mLength, $nLength);
}
sub wikiBacktrack
{
@C = @{$_[0]};
@m = @{$_[1]};
@n = @{$_[2]};
$mLength = $_[3];
$nLength = $_[4];
print("\n $n[5] \n");
#BACKTRACKIN BB
if($mLength==0 || $nLength==0)
{
return ("");
} elsif($m[$mLength] eq $n[$nLength])
{
return &wikiBacktrack(@C, @m, @n, $mLength-1, $nLength-1) + $m
+[$mLength];
} else
{
if($C[$mLength][$nLength-1] > $C[$mLength-1][$nLength])
{
return &wikiBacktrack(@C, @m, @n, $mLength, $nLength-1);
} else
{
return &wikiBacktrack(@C, @m, @n, $mLength-1, $nLength);
}
}
}
Any help would be greatly appreciated.
Thanks in advance!