Building on japhy's regex, this seems to work and it's fairly simple, though I haven't tested it's efficiency. It returns undef if there is no common substring.

Caveat: The strings mustn't contain nulls.

#! perl -slw
use strict;

sub lcs{
    my $strings = join "\0", @_;
    my $lcs;
    for my $n ( 1 .. length $strings ) {
        my $re = "(.{$n})" . '.*\0.*\1' x ( @_ - 1 );
        last unless $strings =~ $re;
        $lcs = $1
    }
    return $lcs;
}

my @a = <DATA>;
chomp @a;

print "lcs: ", lcs( @a );

__DATA__
The quick brown fox jump over the lazy dog
The quick brown fox jumps over the lazy
jumps over the lazy dog The quick brown fox
quick brown fox jumps over the lazy dog
[download]