in reply to Re^3: LCS efficiency problem
in thread LCS efficiency problem

To find the longest common substring (of words)? Nope. Maybe that's the naïve solution?

Replies are listed 'Best First'.
Re^5: LCS efficiency problem
by BrowserUk (Patriarch) on Jun 07, 2008 at 23:37 UTC

    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:

    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.

      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 = ();
      should be
      @last = @this; @this = ();

      2.

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

      should be removed.

      3.

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

      should be

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

      4. The warning can safely be silenced.