Anonymous Monk has asked for the wisdom of the Perl Monks concerning the following question:
Hello Perl Monks,
I found the following code at
http://www.everything2.com/?node_id=1220896
String: abbacbacccabbacbacccccccccccgcccc
pattern: aabaabcbavcvcbvbvnbmhgfdgf
I looked over the code and it looked good. Any thoughts on why it is not working?
Thanks.
I found the following code at
http://www.everything2.com/?node_id=1220896
It seemed to work when the string and pattern were short (4 or 5 characters) but when I increased the length of the string and pattern, it ran forever. The string I used was:# lcs.pl use strict; use Memoize; sub longerOf { my ($x, $y) = @_; return (length $x > length $y) ? $x : $y; } memoize('lcs'); sub lcs { my ($a, $b) = @_; if ($a eq "" || $b eq ""){ return ""; } my ($az, $bz) = (chop $a, chop $b); if ($az eq $bz){ return lcs($a, $b) . $az; } else { return longerOf( lcs($a . $az, $b), lcs($b . $bz, $a)); } } while (1){ print "1: "; my $a = <>; chomp $a; print "2: "; my $b = <>; chomp $b; print "LCS: ", lcs($a, $b), "\n\n"; }
String: abbacbacccabbacbacccccccccccgcccc
pattern: aabaabcbavcvcbvbvnbmhgfdgf
I looked over the code and it looked good. Any thoughts on why it is not working?
Thanks.
|
---|
Replies are listed 'Best First'. | |
---|---|
Re: Longest Common SubSequence Not Working Correctly
by moritz (Cardinal) on Nov 12, 2007 at 23:23 UTC | |
Re: Longest Common SubSequence Not Working Correctly
by Anonymous Monk on Nov 13, 2007 at 01:32 UTC | |
by blokhead (Monsignor) on Nov 13, 2007 at 20:01 UTC | |
by Anonymous Monk on Nov 14, 2007 at 05:16 UTC | |
by blokhead (Monsignor) on Nov 14, 2007 at 14:58 UTC | |
by Anonymous Monk on Nov 15, 2007 at 00:49 UTC | |
by moritz (Cardinal) on Nov 13, 2007 at 07:54 UTC | |
Re: Longest Common SubSequence Not Working Correctly
by Limbic~Region (Chancellor) on Nov 16, 2007 at 02:27 UTC |
Back to
Seekers of Perl Wisdom