There's a lot of different approaches to searching small alphabets. The one you linked to maintains state during the search loop to get bigger shifts, and comp

There's a lot of different approaches to searching small alphabets. The one you linked to maintains state during the search loop to get bigger shifts, and complexity in search loops always slows it down, sometimes to the point there is a net loss. If the needle was reasonably long, which is not uncommon for low alphabet needles, I suspect a better approach would be to use a hash based Horspool style algorithm working on n-grams, say 4. This works by calculating shifts based on ngrams, rather than individual bytes. Since there are many more permutations, you effectively increase the alphabet and hence the shifts also increase. At the cost of always having to read an entire ngram before you can shift. Edit: you also hash the ngram into a smaller hash table of course, you don't maintain a shift position for each ngram. You can tune the size of the hash table for lower memory or higher performance. This is similar to the multi pattern Wu Manber search, but applied to a single needle. Edit 2: I have found this algorithm also beats Horspool most of the time, say for an ngram size of 2 or 3, on any alphabet, not just low ones.