Sorry for the false start, hopefully this does the job.

#! perl -slw
use strict;
use List::Util qw[ reduce ];

sub longestComposite{
    my( $string, $qRef ) = @_;
    my $copy = ' ' x length $string;

    $string =~ s[($_)]{
        my $len = length $1;
        substr( $copy, pos( $string ), $len ) = $1;
        $1;
    }ge for @$qRef;

    return reduce{ 
          length $a > length $b ? $a : $b 
    } split ' ', $copy;
}

my $string ="EICHENBAUMSCHULE";
my @query = qw( EIC BAUM UMS CHU LE );

print longestComposite( $string, \@query );

__END__
P:\test>366569
BAUMSCHULE
[download]

No promises about efficiency if you're doing this on large volumes of data.