note roboticus [lindsay_grey]: I've been plunking around for about 4 hours on this one (it's an interesting problem!). I first built a test data generator to generate some datasets. <readmore> <c> #!/usr/bin/perl # # gen_random_string.pl <CNT> <SYMS> <minlen> <maxlen> # # Generate <CND> random strings between <minlen> and <maxlen> characters # using only the characters in <SYMS>. # use strict; use warnings; my $cnt = shift; my $SYMS = shift; my $min = shift; my $max = shift or die usage('Missing args!'); die "CNT ('$cnt') must be numeric!\n" if $cnt =~ /[^0-9]/; die "MIN ('$min') must be numeric!\n" if $min =~ /[^0-9]/; die "MAX ('$max') must be numeric!\n" if $max =~ /[^0-9]/; die "SYMS must be longer than 0 characters!\n" if length($SYMS) < 1; if ($min>$max) { print "Min must be <= Max, swapping!\n"; my $t=$min; $min=$max; $max=$t; } my @syms = split //,$SYMS; #print join(", ", @syms),"\n"; while ($cnt) { my $len=$min + int(($max-$min)*rand); my $t=''; $t .= $syms[int(rand(@syms))] for 1 .. $len; print "$t\n"; --$cnt; } </c> </readmore> My primary datasets are 100, 200, 500, 1000, 2000, 5000 and 10000 strings each, where the strings are between 15 and 25 characters long. I generated them like: <c> $ for J in {1,2,5}0{0,00,000}; do echo $J; perl gen_random_string.pl $J ACGTN 15 25 >t.$J; done </c> I next created a trivial brute-force solver: <readmore> <c> #!/usr/bin/perl # # multi-string-match_brute_force.pl <FName> # use strict; use warnings; use feature ':5.10'; my $fname = shift; open my $FH, '<', $fname or die; my @candidates = <$FH>; @candidates = grep { /^[ACGTN]+$/ } # delete the comments map { s/^\s+//; s/\s+$//; $_ } @candidates; my $start = time; @candidates = sort { length($a) <=> length($b) || $a cmp $b } @candidates; my @unique; my $cnt_dup=0; OUTER: while (my $t = shift @candidates) { for my $u (@unique) { if ($t =~ /$u/) { ++$cnt_dup; next OUTER; } } push @unique, $t; } my $end = time - $start; print scalar(@unique), " unique items.\n"; print "$cnt_dup rejected.\n"; print "$end seconds\n"; </c> </readmore> The brute force solver told me that all my datasets contained only unique strings. So I created some datasets with plenty of duplicates: <c> $ cat t.100 t.100 t.100 > t.300 $ cat t.1000 t.1000 t.1000 > t.3000 $ cat t.10000 t.10000 t.10000 > t.30000 $ cat t.100 t.300 > t.400 $ cat t.1000 t.3000 > t.4000 $ cat t.10000 t.30000 > t.40000 </c> I've been monkeying with some different bits, but my best two (so far) give me the times: <c> num brute strings force Robo1 Robo2 ------- ------- ----- ----- 100 .125 .125 .110 200 .234 .172 .125 300 .202 .141 .110 400 .234 .156 .110 500 1.030 .187 .125 1000 3.916 .265 .188 2000 15.288 .390 .265 3000 11.435 .546 .328 4000 15.319 .656 .422 5000 93.600 .858 .546 10000 377.412 1.638 1.029 20000 3.151 1.981 30000 4.493 2.621 40000 5.866 3.417 50000 4.929 </c> I then created a few datasets with strings between 200 and 300 characters to see how my better one did: <c> # str Robo2 Notes ------ ------ -------------- 1000 0.687 unique 2000 1.264 1000 unique 10000 6.412 unique 20000 11.887 10000 unique 100000 65.224 unique 200000 126.190 100000 unique </c> I'll wait a little while before posting my solution, as I don't want to spoil things for people still working on it right now. ...[roboticus] When your only tool is a hammer, all problems look like your thumb. 906020 906020