Three ideas: First, try the bitap algorithm. Second, you can encode the search as a DFA - look up the Aho–Corasick algorithm. Then just run the DFA over the g

Three ideas: First, try the bitap algorithm. Second, you can encode the search as a DFA - look up the Aho–Corasick algorithm. Then just run the DFA over the genome. It means that you don't need to match every string at every position. If you've read AAAAA and your string starts with CCCCC with an edit distance of 4, you can skip ahead for a while before you need to start reading again. Third, you could build a suffix tree (O(n) preprocessing), and then use the standard fuzzy string matching algorithm using suffix trees on it.