In case Itatsumaki should ever come back. Here's a somewhat improved implementation of my Xor algorithm. The original projection of 3 1.2 years runtime to process 100,000 x 1,000 x 30,000 is now reduced to 7.6 days:

Update (2004/12/08): Updated code to correct an error that manifested itself when the sequences were not an exact multiple of the key length. (As noted below by demerphq)

#! perl -slw
use strict;
use bytes;

our $FUZZY ||= 2;

open KEYS, '<', $ARGV[ 0 ] or die "$ARGV[ 0 ] : $!";
my @keys = <KEYS>;
close KEYS;
chomp @keys;
warn "Loaded ${ \scalar @keys } keys";

open SEQ, '<', $ARGV[ 1 ] or die "$ARGV[ 1 ] : $!";

my( $masked, $pos );

my $totalLen = 0;
my $count = 0;

while( my $seq = <SEQ> ) {
    chomp $seq;
    my $seqLen = length $seq;
    $totalLen += $seqLen;
    
    for my $key ( @keys ) {
        my $keyLen     = length $key;
        my $mask       = $key x ( int( $seqLen / $keyLen ) + 1 );
        my $maskLen    = length $mask;
        my $minZeros   = chr( 0 ) x int( $keyLen / ( $FUZZY + 1 ) );
        my $minZlen       = length $minZeros;

        for my $offset1 ( 0 .. $keyLen-1 ) { 
            $masked =  $mask ^ substr( $seq, $offset1, $maskLen );

            $pos = 0;
            while( 
                $pos = 1+index  $masked, $minZeros, $pos 
            ) {
                $pos--;
                my $offset2 = $pos - ($pos % $keyLen );
                last unless $offset1 + $offset2 + $keyLen <= $seqLen;
                
                my $fuz = $keyLen 
                    - ( substr( $masked, $offset2, $keyLen ) =~ tr[\0]
+[\0] );
                if( $fuz <= $FUZZY ) {
                    printf "\tFuzzy matched key:'$key' -v- '%s' in lin
+e:"
                        .  "%2d @ %6d (%6d+%6d) with fuzziness: %d\n",
+ 
                        substr( $seq, $offset1 + $offset2, $keyLen ),
                        $., $offset1 + $offset2, $offset1, $offset2, $
+fuz;
                }
                $pos = $offset2 + $keyLen;
            }
        }
    }
}
warn "\n\nProcessed $. sequences";
warn "Average length: ", $totalLen / $.;
close SEQ;
[download]

A coupe of runs (on single sequences for timing purposes) on data comparable (produced by the same code) as other timings published elsewhere:

[ 6:57:56.46] P:\test\demerphq>
..\406836-3 
Fuzz-Words-W0025-S100000-WC100000-SC0001.fuzz 
Fuzz-Strings-W0025-S100000-WC100000-SC0001.fuzz

Loaded 100000 keys at P:\test\406836-3.pl line 12.
seq:00001 (100000)
  1 @  69364 (    14+ 69350) with fuzziness: 0
  1 @  24886 (    11+ 24875) with fuzziness: 0
  1 @  40056 (     6+ 40050) with fuzziness: 0
  1 @  68870 (    20+ 68850) with fuzziness: 0
  1 @   3264 (    14+  3250) with fuzziness: 0
  1 @   8744 (    19+  8725) with fuzziness: 0
  1 @   7493 (    18+  7475) with fuzziness: 0
  1 @  28209 (     9+ 28200) with fuzziness: 0
  1 @  91337 (    12+ 91325) with fuzziness: 0
  1 @  63018 (    18+ 63000) with fuzziness: 0
  1 @  61025 (     0+ 61025) with fuzziness: 0
  1 @  32114 (    14+ 32100) with fuzziness: 0
  1 @  30461 (    11+ 30450) with fuzziness: 0
  1 @  59174 (    24+ 59150) with fuzziness: 0
  1 @  74084 (     9+ 74075) with fuzziness: 0
  1 @  58322 (    22+ 58300) with fuzziness: 0
  1 @  78465 (    15+ 78450) with fuzziness: 0
  1 @  56190 (    15+ 56175) with fuzziness: 0
  1 @  14968 (    18+ 14950) with fuzziness: 0
  1 @  31986 (    11+ 31975) with fuzziness: 0
  1 @  60748 (    23+ 60725) with fuzziness: 0
  1 @  93369 (    19+ 93350) with fuzziness: 0
  1 @   6242 (    17+  6225) with fuzziness: 0
  1 @  15282 (     7+ 15275) with fuzziness: 0
  1 @  13293 (    18+ 13275) with fuzziness: 0


Processed 1 sequences at P:\test\406836-3.pl line 57, <SEQ> line 1.
Average length: 100000 at P:\test\406836-3.pl line 58, <SEQ> line 1.

[ 7:28:22.37] P:\test\demerphq>

[ 8:36:32.71] P:\test\demerphq>
..\406836-3 
Fuzz-Words-W0025-S1000-WC100000-SC0010.fuzz 
Fuzz-Strings-W0025-S1000-WC100000-SC0010.fuzz

Loaded 100000 keys at P:\test\406836-3.pl line 12.
seq:00001 (01000)
  1 @     94 (    19+    75) with fuzziness: 0
  1 @    692 (    17+   675) with fuzziness: 0
  1 @    326 (     1+   325) with fuzziness: 0
  1 @     35 (    10+    25) with fuzziness: 0
  1 @    826 (     1+   825) with fuzziness: 0
  1 @    598 (    23+   575) with fuzziness: 0
  1 @    860 (    10+   850) with fuzziness: 0
  1 @    489 (    14+   475) with fuzziness: 0
  1 @    370 (    20+   350) with fuzziness: 0
  1 @    745 (    20+   725) with fuzziness: 0
  1 @    297 (    22+   275) with fuzziness: 0
  1 @    415 (    15+   400) with fuzziness: 0
  1 @    119 (    19+   100) with fuzziness: 0
  1 @    957 (     7+   950) with fuzziness: 0
  1 @    646 (    21+   625) with fuzziness: 0
  1 @    779 (     4+   775) with fuzziness: 0


Processed 1 sequences at P:\test\406836-3.pl line 57, <SEQ> line 1.
Average length: 1000 at P:\test\406836-3.pl line 58, <SEQ> line 1.

[ 8:36:54.42] P:\test\demerphq>
[download]