I recently had a similar problem and I was to write a post to ask comments about the solution - go figure! I needed to do tests for much less elements than you (around 10000 entries), but I didn't like the idea of a raw array search, while holding the commitment to Keep It Simple (Stupid).

I used a HoH in which the first key is the length of the string to be tested; when I have to check for existence, I iterate through lengths and test existence in each sub-hash.

# Use an HoH instead of simple array
my %categories;
foreach (@sub) {
   $categories{length($_)}{$_} = undef;
}

# ... when you need it...
sub matches_any {
   my $t = shift;
   foreach my $len (keys %categories) { # We could also sort here...
      return 1 if exists $categories{$len}{substr($t, 0, $len)};
   }
   return 0;
}
[download]

Note that in my problem I know that the incoming strings are always longer than those I run tests against, so I skipped testing if length($t) is actually greater or equal to $len. Moreover, I don't have a big variance in lengths, so $len should span few values.