$hash{'Ge'} = ['George', 'George Bush'];
[download]

Also, study might be your friend for this, if you use a regex rather than index.

my $re = join '|', @sub;
$re = qr/($re)/;
$str =~ $re;
[download]

Dave.

very large regexes can be even more inefficient. when i say large list, think hundreds or thousands of strings.

Check out Regexp::PreSuf and Regexp::Assemble. They combine lists of words or patterns into a hopefully more efficient pattern than a trivial ORed expression.

ihb

as noted in Regexp:Assemble:

You should realise that large numbers of alternations are processed in perl's regular expression engine in O(n) time, not O(1). If you are still having performance problems, you should look at using a trie.

regexes are often more convenient, rather than efficient. but thanks for pointing me there, because the note also mentions:

... Perl's own regular expression engine will implement trie optimisations in perl 5.10 (they are already available in perl 5.9.3 if you want to try them out).

this would probably solve the problem in the future, but i need to find something for the present.

For the present you can/should use R::A or one of the other regex modules as they should be patched in time of 5.10 to utilize the TRIE optimisation if possible. OTOH You havent really spelled out if you mean an anchored match or not. Ie is it /^(list|of|strings)$/ or is it /^(list|of|strings)/ or is it /(list|of|strings)/? Depending on which there may be non regex based strategies that are quite competitive.

---
$world=~s/war/peace/g

In the case of your searches, I'd have to ask how many items you have, and how many of those items are subsets of items. (eg, if 'George' fails, there's no reason to test for 'George Bush' ... as the list gets larger, there's a better chance of this coming up) And even if they aren't in there directly, we may have other cheats. (no 'G' in the item? Well, then neither of the items will match... a simple test may be able to strip out large sections of your list)

Then we have the question of how many input strings you're searching, in relationship to the number of substrings. (if we're searching only one input string per invocation, we lose if we spend too much time trying to pre-process the list of substrings)

Also, what is the overall purpose, and does the order of the initial list matter? (for instance -- if we're using it in a switch() statement, once we've found the first match, we don't continue... but we need to make sure the list order doesn't change, or we'll potentially have inconsistent results if more than one list item matches)

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]

my @results = grep { $str =~ /$_/ } @sub;
[download]

This might be more efficiently done in C++.

EDIT: How efficient do you need to be? Searching a 100,000-character string for 100,000 10-character substrings took me 57 seconds -

use strict;
use warnings;

my ($input, $str, @str, $t);

$input .= chr(97 + int rand 26) for 1..100000;
for (1..100000) {
    $str = '';
    $str .= chr(97 + int rand 26) for 1..10;
    push @str, $str;
}
$t = time();
for (@str) {
    print "$_\n" if index($input, $str) != -1;
}
print time() - $t;
[download]