This achieves the AND requirement, but note the possibility of false matches if there is overlap between the two words (3rd example):

[0] Perl> $re = qr[(?=^.*this)(?=^.*that)];;
[0] Perl> $_ =~ $re and print "$_ matched" 
          for qw[thisthat thatthis thathis thisnthat thatnthis];;
thisthat matched
thatthis matched
thathis matched **
thisnthat matched
thatnthis matched
[download]