Re^5: LCS efficiency problem

I'm sorry. I looked at the code, but I do not see anything there that suggests that it can achieve the impossible.

Firstly, neither of the routines in the linked post seem to work?

#! perl -slw
use strict;

sub lcs_arrays1 {
    my ( $a1, $a2 ) = @_;
    my @matches;
    my $longest = 0;
    my @last;
    my @this;

    for my $b1 ( 0 .. $#$a1 ) {
        @this = @last;
        @last = ();

        for my $b2 ( 0 .. $#$a2 ) {
            if ( $$a1[$b1] eq $$a2[$b2] ) {
                my @match = ( $$a1[$b1] );
                my $e2 = $b2+1;

                $this[$e2] = $last[$e2-1] + 1;

                if ($this[$e2] > $longest) {
                    $longest = $this[$e2];
                    @matches = ();
                }

                if ($this[$e2] == $longest) {
                    push @matches, [
                       @{$a1}[ ($b1-$longest+1), $b1 ]
                    ];
                }
            }
        }
    }

    return $matches[0]; # array ref -> longest matching list
}

sub lcs_arrays2 {
    my ( $a1, $a2 ) = @_;
    my @match;
    my $longest = 0;
    my @last;
    my @this;

    for my $b1 ( 0 .. $#$a1 ) {
        @this = @last;
        @last = ();

        for my $b2 ( 0 .. $#$a2 ) {
            if ( $$a1[$b1] eq $$a2[$b2] ) {
                my @match = ( $$a1[$b1] );
                my $e2 = $b2+1;

                $this[$e2] = $last[$e2-1] + 1;

                if ($this[$e2] > $longest) {
                    $longest = $this[$e2];
                    @match = @{$a1}[ ($b1-$longest+1), $b1 ];
                }
            }
        }
    }

    return \@match; # array ref -> longest matching list
}

my @a = ( 'a'..'d' );
my @b = ( 'b'..'d' );

print 'v1: ',  @{ lcs_arrays1( \@a, \@b ) };
print 'v2: ',  @{ lcs_arrays2( \@a, \@b ) };

__END__
C:\test\690326>ikegami.pl
Use of uninitialized value in addition (+) at C:\test\690326\ikegami.p
+l line 20.
Use of uninitialized value in addition (+) at C:\test\690326\ikegami.p
+l line 20.
Use of uninitialized value in addition (+) at C:\test\690326\ikegami.p
+l line 20.
v1: bb
Use of uninitialized value in addition (+) at C:\test\690326\ikegami.p
+l line 55.
Use of uninitialized value in addition (+) at C:\test\690326\ikegami.p
+l line 55.
Use of uninitialized value in addition (+) at C:\test\690326\ikegami.p
+l line 55.
v2:
[download]

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.

"Science is about questioning the status quo. Questioning authority".

In the absence of evidence, opinion is indistinguishable from prejudice.

"Too many [] have been sedated by an oppressive environment of political correctness and risk aversion."

Comment on Re^5: LCS efficiency problem Download Code

Replies are listed 'Best First'.
Re^6: LCS efficiency problem by ikegami (Patriarch) on Jun 08, 2008 at 01:21 UTC
Some small problems needs to be fixed. They're listed below, but I've updated the original as well (to do the impossible!). 1. `@this = @last; @last = ();` [download] should be `@last = @this; @this = ();` [download] 2. `my @match = ( $$a1[$b1] );` [download] should be removed. 3. `@{$a1}[ ($b1-$longest+1), $b1 ]` [download] should be `@{$a1}[ ($b1-$longest+1) .. $b1 ]` [download] 4. The warning can safely be silenced.	[reply] [d/l] [select]

Replies are listed 'Best First'.

Re^6: LCS efficiency problem
by ikegami (Patriarch) on Jun 08, 2008 at 01:21 UTC

Some small problems needs to be fixed. They're listed below, but I've updated the original as well (to do the impossible!).

        @this = @last;
        @last = ();
[download]

        @last = @this;
        @this = ();
[download]

my @match = ( $$a1[$b1] );
[download]

should be removed.

@{$a1}[ ($b1-$longest+1), $b1 ]
[download]

should be

@{$a1}[ ($b1-$longest+1) .. $b1 ]
[download]

4. The warning can safely be silenced.

[reply]
[d/l]
[select]