For some definition of "matches", the basic algorithm is

my @out;

for my $i (@in) {
   my $delete = 0;
   for my $d (@dels) {
      if (matches($i, $d)) {
         $delete = 1;
         last;
      }
   }
   push @out, $i if !$delete;
}
[download]

In your original question, you asked for equality, so "matches($i, $d)" would be "$i eq $d".

In your updated question, you asked for substring presence, so "matches($i, $d)" would be "index($i, $d) >= 0" or "$i =~ /\Q$d\E/".

The hash solution and the build-a-regexp solution are simply optimizations of the above algorithm.