in reply to Re: LCS efficiency problem
in thread LCS efficiency problem
sub lcs_arrays { my ( $a1, $a2 ) = @_; my @matches = [ 0, -1 ]; my $longest = 0; my @last; my @this; for my $b1 ( 0 .. $#$a1 ) { @last = @this; @this = (); for my $b2 ( 0 .. $#$a2 ) { if ( $$a1[$b1] eq $$a2[$b2] ) { my $e2 = $b2+1; $last[$e2-1] ||= 0; $this[$e2] = $last[$e2-1] + 1; if ($this[$e2] > $longest) { $longest = $this[$e2]; @matches = (); } if ($this[$e2] == $longest) { push @matches, [ ($b1-$longest+1), $b1 ]; } } } } my ($beg, $end) = @{$matches[0]}; return [ @{$a1}[ $beg..$end ] ]; }
Or since you're only returning one of the longest,
sub lcs_arrays { my ( $a1, $a2 ) = @_; my $beg = 0; my $end = -1; my $longest = 0; my @last; my @this; for my $b1 ( 0 .. $#$a1 ) { @last = @this; @this = (); for my $b2 ( 0 .. $#$a2 ) { if ( $$a1[$b1] eq $$a2[$b2] ) { my $e2 = $b2+1; $last[$e2-1] ||= 0; $this[$e2] = $last[$e2-1] + 1; if ($this[$e2] > $longest) { $longest = $this[$e2]; $beg = $b1-$longest+1; $end = $b1; } } } } return [ @{$a1}[ $beg..$end ] ]; }
Update: Tested. Added fixes.
|
|---|