That is only 75 states for a string of length 25 with two errors allowed.

That is for one search key. There are 100,000 to process. Against 30,000 x 1000-char strings.

The "... the complexity of this problem." I spoke of with respect to a DFA, is the idea that you could combine all 100,000 keys into a single, huge DFA.

If you applied your code above--or any pure perl implementation of a DFA--against each of the 30,000 strings, for each of the 100,000 keys, would it out-perform Perl's regex engine?

Even if you coded seperate, 75-state DFA using C for each of the 100,000 keys, and then applied them to the 30,000 sequences, would it out perform Perl's regex engine?

Do you fancy the task of hand coding 100,000 75-state DFAs in C? And then doing it again next week for another 100,000 keys?.

Obviously, you wouldn't hand-code all the DFAs individually. You would write a DFA generator and let the computer do the work**. Writing DFA generators is non-trivial, Even once you have it working, you still have to apply 100,000 DFAs to each of the 30,000 sequences.

So, rather than generate individual DFAs, you write your generator to build one, humungous DFA that encapsulates the state of all, 75 states of all 100,000 keys. Combining the DFA this way probably reduces the 7.5 million states to less that 10%? That's still an awefully complex DFA to generate, and an even more complex DFA generator to design, code, test, debug--in C.

If you did do this, the advantage is that you only have one DFA to apply to the 30,000 sequences, which would almost certainly be the quickest of all the techniques described in this thread. It's just a case of doing the work.

**Does this sound familiar? If you carefully craft your regexes to avoid backtracking, you are using the regex engine to generate a fairly close approximation to a custom DFA for each regex. No, horribly compex, difficult to get right, C work to do. It's already available in Perl.