I would suggest starting by ordering your array by string length, shortest to longest. Then, take element 0 as your first approximation at the shortest substring and compare it to the same length section (via substr()) to the next string. If they do not match, reduce the test sequence until you arrive at a match, or an empty string. Repeat until you have examined all strings, or have an empty approximation string.

Untested code example:

my @string 
  = sort { length $a <=> length $b }
  ( qw/ quux asdfasdfasdf asdfasdf asdfzxcv as / );
my $common = shift @string;
while ( my $teststr = shift @string and length $common ) {
    if ( $common eq substr( $teststr, 0, length $common ) ) {
        next;
    }
    my $flag = length $common;
    while ( $flag ) {
        if ( $common eq substr( $teststr, 0, $flag ) ) {
            $flag = 0;
        }
        else {
            $flag--;
            $common = substr( $common, 0, $flag );
        }
    }
}
# print $common;
[download]

Hope that helps.

Update: 2015-11-15
Fixed errors in code sample. (My thanks to oiskuu for pointing their existence!)