in reply to Longest Common Substring

Probably not the most efficient implementation (and maybe incomplete), but if you can't get the modules to work, you could wrap this up as a subroutine. 

#! perl -slw
use strict;
use Data::Dumper;

my $needle = 'the lazy cat';
my $haystack = 'the quick brown fox jumps over the lazy dog';
my @matches;


for my $start (0..length $needle) {
    for my $len ($start+1 .. length $needle) {
        my $substr = substr($needle, $start, $len);
        push @matches, $haystack =~ m[($substr)]g;
    }
}

my ($len, $longest) = 0;

length > $len and ($longest, $len) = ($_, length) for @matches;

print "The longest common substring between\n", $needle, "\nand\n", $h
+aystack, "\nis '$longest'";
__END__
C:\test>249239.pl
The longest common substring between
the lazy cat
and
the quick brown fox jumps over the lazy dog
is 'the lazy '

C:\test>

[download]
Examine what is said, not who speaks.
1) When a distinguished but elderly scientist states that something is possible, he is almost certainly right. When he states that something is impossible, he is very probably wrong.
2) The only way of discovering the limits of the possible is to venture a little way past them into the impossible
3) Any sufficiently advanced technology is indistinguishable from magic.
Arthur C. Clarke.

Replies are listed 'Best First'.
Re: Re: Longest Common Substring
by Enlil (Parson) on Apr 09, 2003 at 19:15 UTC
    BrowserUK's solution doesn't quite work I tried the following and did not get back what was expected ( " the quick brown fox "):
    my $needle = 'i pushed the lazy dog into a creek, the quick brown fox 
+told me to';
my $haystack = 'the quick brown fox jumps over the lazy dog';

    [download]
    and got back 'the lazy dog' (it works if you reverse the $needle and the $haystack.

    But to his credit it seems to work better than String-LCSS-0.10, and he did mention that it might be incomplete (run it both ways, get the longest string and print that, I believe should give you the most right answer, but my tests might also be incomplete).

    Where which running the following code:

    Read more... (673 Bytes)

    I would use Algorithm-Diff using this part of the documentation as a starting point.

    Note: The Author of String-LCSS-0.10 has been notified.

    -enlil

[reply]
[d/l]
[select]

In Section Seekers of Perl Wisdom