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]