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]

Enlil's right, my code was a bit slovenly. I believe this is both more correct and more efficient, but I can't guarentee it doesn't fail on some edge case or another.

#! perl -slw
use strict;

sub lcss (\$\$) {
    my ($needle, $haystack) = @_;
    ($needle, $haystack) = ($haystack, $needle)
        if length $$needle > length $$haystack;

    my ($longest_c, $longest) = 0;
    for my $start (0..length $$needle) {
        for my $len ( reverse $start+1 .. length $$needle) {
            my $substr = substr($$needle, $start, $len);
            length $1 > $longest_c and ($longest_c, $longest) = (lengt
+h $1, $1)
                while $$haystack =~ m[($substr)]g;
        }
    }
    return $longest;
}

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

print "The longest common substring between\n"
    , $needle, "\nand\n"
    , $haystack, "\nis '"
    , lcss($needle, $haystack)
    , "'";

$needle = 'i pushed the lazy dog into a creek, the quick brown fox tol
+d me to';
$haystack = 'the quick brown fox jumps over the lazy dog';

print "The longest common substring between\n"
    , $needle, "\nand\n"
    , $haystack, "\nis '"
    , lcss($needle, $haystack)
    , "'";

__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 '

The longest common substring between
i pushed the lazy dog into a creek, the quick brown fox told me to
and
the quick brown fox jumps over the lazy dog
is 'the quick brown fox '
[download]

If it was more than a single function it would've been impossible for me to do since the guy who wrote it used swig, and well, swig on win32 hasn't been working out for me. I ended up writing an XS port (pretty easily I might add), and the source can be found at http://crazyinsomniac.perlmonk.org/perl/files/String-Ediff-0.01.tar.gz.