Beefy Boxes and Bandwidth Generously Provided by pair Networks
Clear questions and runnable code
get the best and fastest answer
 
PerlMonks  

longest common substring

by flaviusm (Acolyte)
on Dec 31, 2007 at 19:47 UTC ( #659792=perlquestion: print w/ replies, xml ) Need Help??
flaviusm has asked for the wisdom of the Perl Monks concerning the following question:

Hi,

I am using String::LCSS module to find the longest common substring of two strings and I don't get the result I am expecting. Can anybody tell me what am I doing wrong? Thank you.

#!/usr/bin/perl require String::LCSS; $s1 = '1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 2 18 19 20 21 22 23 7 + 24'; $s2 = '1 2 3 4 5 7 8 9 11 12 13 10 14 15 16 17 2 18 19 20 21 22 23 7 2 +4'; $result = String::LCSS::lcss ($s1, $s2); print $result;

I am expecting to get "14 15 16 17 2 18 19 20 21 22 23 7 24" but I get instead " 11 12 13 1"

Comment on longest common substring
Download Code
Replies are listed 'Best First'.
Re: longest common substring
by Limbic~Region (Chancellor) on Dec 31, 2007 at 20:13 UTC
      For more than 2 strings, I'd also suggest Tree::Suffix (although I've never used this module. It is just in theory the best algorithm).
        lima1,
        The original thread I referenced was for longest common subsequence. I still have yet to find an implementation for finding the longest common subsequences for > 2 strings other than the one I posted. I adapted it for common substrings to show it was possible. I would definitely use and recommend Tree::Suffix now that I know about it. I mentioned my home grown implementation in this thread in case the XS version of the module flaviusm was using was also broken. Thanks!

        Cheers - L~R

Re: longest common substring
by wind (Priest) on Dec 31, 2007 at 20:25 UTC
    This appears to be a bug in the module. If you append ' 25' and ' 26' to $s1 and $s2 respectively, the function works as expected. I would suggest that you follow L~R's advice and give String::LCSS_XS a try, as it's 4 years more current.

    - Miller

      I just installed the module you suggested and it works as expected.

      Thank you very very much Miller and L~R

        I would hope that it is actually returning a space in front of the value that you said that you were expecting. Though, the documentation for String::LCSS is so minimal that I'd be wary of making any assumptions at all about what it does without first digesting the source code.

        - tye        

Re: longest common substring
by Khen1950fx (Canon) on Dec 31, 2007 at 21:44 UTC
    I followed Limbic~Region's advice and used String::LCSS_XS.
    #!/usr/bin/perl use strict; use warnings; use String::LCSS_XS qw(lcss lcss_all); my @result = lcss ( '1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 2 18 19 20 21 22 23 7 2 +4', '1 2 3 4 5 6 7 8 9 11 12 13 10 14 15 16 17 2 18 19 20 21 22 23 7 2 +4'); print "$result[0]\n";

Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others lurking in the Monastery: (14)
As of 2015-09-04 16:58 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    My preferred temperature scale is:










    Results (143 votes), past polls