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]