This exact problem is actually covered in the panther book as an eval() example. The code is basically like yours, but the if() statement is built with a join() command:

@patterns = qw(cat dog);
$code = 'if (/';
$code .= join('/ && /', @patterns);
$code .= '/) {
   print "Found a DOG and a CAT!\n\n";
}';
eval $code;
die "Error: $@" if ($@);
[download]

Here's another solution which probably has no practical application, but looks cool anyway:

#!/usr/bin/perl

use strict;

my (@str, @search, %words, @matched_words);

# Token string
@str = qw(cat dog rat elephant giraffe);

# List of search keys to check for
@search = qw(cat dog);

# Create a hash keyed with the token list.
# E.g. $words{elephant} = 1; $words{rat} = 1; etc
@words{@str} = (1) x @str;

# Create an array with the same number of elements
# as the number of search keys that were present in
# the original string.
@matched_words = @words{@search};

# Check to see if the number of matched words
# is equal to the number of words we were searching
# for
if (scalar @search == scalar @matched_words)
{
        print "Found a DOG and a CAT!\n\n";
}
[download]

It's case-sensitive and doesn't do regular expressions, but I imagine it's pretty fast.

-Matt