P is for Practical | |
PerlMonks |
Re: finding longest common substring (ALL common substrings)by BrowserUk (Patriarch) |
on Nov 20, 2003 at 06:20 UTC ( [id://308521]=note: print w/replies, xml ) | Need Help?? |
Broken code WarningThe code below is broken! Please see Re: Re: Re: finding longest common substring (ALL common substrings) for details, and the update at the bottom for a couple of 'fixed' versions. This will never win the "fastest longest common substring" accolade, but it is interesting in that in a list context, it returns a list of all common substring sorted by length (longest first). I was also surprised how simple it was to code, and fairly surprised by how efficient it was given what it does.
Update: The following two versions work, in as much as they will return the longest common substring if called in a scalar context. They will also return all common substrings (ordered longest to shortest) when called in a list context. As lcs routines, they are both slow, with lcs3() being marginally quicker than lcs2(). I'm not sure how they compare performance-wise with other mechanism for generating all common substrings. As implemented, they also do not preserve the value of two (unavoidable?) globals %subs & $n. This could be fixed by judicious use of local if it is of concern.
Whether the above code has any merits I'm not sure, but it's here should anyone find a good use for it. Examine what is said, not who speaks.
"Efficiency is intelligent laziness." -David Dunham"Think for yourself!" - Abigail Hooray! Wanted!
In Section
Seekers of Perl Wisdom
|
|