###########################
#      Match::LCS.pm      #
#      Version 1.01       #
#    (c) Ed Egan 2009     # 
###########################

package LCS;
use strict;
use warnings;

sub new {
    my $class = shift;
    my $self = bless {}, $class;
    return $self;
}

sub LCS {
    my $self=shift;
    my $Str1=shift;
    my $Str2=shift;
    my ($LengthStr1, $LengthStr2) = (length($Str1), length($Str2));
    my @a;
    my $Cur = 0;
    my $Next = 1;
    for (0..$LengthStr2) {
        $a[$Cur][$_] = 0;
        $a[$Next][$_] = 0;
    }
    my ($t, $iPlus1, $jPlus1);
    for my $i (0..$LengthStr1 - 1) {
    	$a[$Next][0] = 0;
    	$iPlus1 = $i + 1;
        for my $j (0..$LengthStr2 - 1) {
            $jPlus1 = $j + 1;
    	    $t = $a[$Cur][$j] + ((substr($Str1, $i, 1) eq substr($Str2, $j, 1)) ? 1 : 0);
    	    $a[$Next][$jPlus1] = 0;
    	    if ($a[$Cur][$jPlus1] > $a[$Next][$jPlus1]) { $a[$Next][$jPlus1] = $a[$Cur][$jPlus1]; }
    	    if ($a[$Next][$j] > $a[$Next][$jPlus1]) { $a[$Next][$jPlus1] = $a[$Next][$j]; }
    	    if ($t > $a[$Next][$jPlus1]) { $a[$Next][$jPlus1] = $t; }
        }
        $Cur=1-$Cur; $Next=1-$Next;
    }
    return $a[$Cur][$LengthStr2];
}

1;
