Well, here's a regexp based approach. Of course if you know in advance that a certain charachter or substring won't ever be in your data, you can avoid the $sep machinery:

sub common {
    my $sep='';
    $sep |= $_ for map /:+/g, @_;
    $sep="<$sep:>";
    local $_=join $sep, @_;
    /^(.*)(.*)$sep\1(.*)/;
}
[download]

Update: I hadn't noticed that you were focusing on efficiency. And from that POV I'm quite confident that this solution won't score very well. But as far as your concern about your code looking like C goes, this is certainly more perlish. Incidentally I would have used myself an approach like Corion's one but probably matching on /[^\0]/, using pos and substr instead of unpack.