http://qs321.pair.com?node_id=690627


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

Starting with 1 is part of the dynamic programming algorithm, no bug. 
 my @S = (undef, map { lc } split(/\w+/, $s));

[download]
should fix the wordlists (so that eq is enough). Further filtering as suggested below is a good idea, do that!

Replies are listed 'Best First'.
Re^3: LCS efficiency problem
by ikegami (Patriarch) on Jun 06, 2008 at 18:31 UTC

    Oops, missed the undef.

    But note that starting at one has nothing to do with the dynamic programming technique. If you wanted to start at zero (say if @S and @T are inputs to the function), then just replace 

                   $L[$i-1][$j-1] ||= 0;
               $L[$i][$j] = $L[$i-1][$j-1] + 1;

    [download]
    with 
                   if ($i && $j) {
                  $L[$i-1][$j-1] ||= 0;
                  $L[$i][$j] = $L[$i-1][$j-1] + 1;
               } else {
                  $L[$i][$j] = 1;
               }

    [download]
[reply]
[d/l]
[select]

In Section Seekers of Perl Wisdom