Beefy Boxes and Bandwidth Generously Provided by pair Networks
Welcome to the Monastery
 
PerlMonks  

Re^2: LCS efficiency problem

by lima1 (Curate)
on Jun 06, 2008 at 07:13 UTC ( #690627=note: print w/replies, xml ) Need Help??


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));
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 (Pope) 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;
    with
    if ($i && $j) { $L[$i-1][$j-1] ||= 0; $L[$i][$j] = $L[$i-1][$j-1] + 1; } else { $L[$i][$j] = 1; }

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://690627]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others contemplating the Monastery: (5)
As of 2021-04-19 13:29 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found

    Notices?