longest common substring

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;
[download]

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
flaviusm, Perhaps you should try String::LCSS_XS since it has been updated recently. Also, I wrote Re^2: Longest Common Subsequence to handle > 2 strings for longest common substrings (though the thread is about subsequences). Cheers - L~R	[reply]
Re^2: longest common substring by lima1 (Curate) on Jan 02, 2008 at 18:41 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).	[reply]
Re^3: longest common substring by Limbic~Region (Chancellor) on Jan 02, 2008 at 19:33 UTC
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	[reply]
Re^4: longest common substring by lima1 (Curate) on Jan 03, 2008 at 07:24 UTC
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	[reply]
Re^2: longest common substring by flaviusm (Acolyte) on Dec 31, 2007 at 21:26 UTC
I just installed the module you suggested and it works as expected. Thank you very very much Miller and L~R	[reply]
Re^3: longest common substring (red card for no green card) by tye (Sage) on Dec 31, 2007 at 21:41 UTC
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	[reply]
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";` [download]	[reply] [d/l]