Let's say you have two sets of 1E8 strings of length 9. The naive algorithm compares all pairs, so it does 1E16 "check if Hamming distance <= 2" calls.

If you group them, first by "first 3 characters equal", then by "middle 3 characters equal", then by "last three characters equal", with a 20-letter alphabet, you will, in each case, get in the order of 1E3 groups each with in the order of 1E5 strings each. Comparing pairs in each groups takes 1E10 "check if Hamming distance <= 2" calls, for a total of 1E13 such calls.

You have to do this 3 times, so this will give you about a factor of 300, assuming the grouping to be free (it isn't, of course, but sorting is O(n log n), and this is a tiny bit simpler)

For longer strings, the speed up increases, though. Length 12 gives you 1E16 vs 10000 groups of 1E4 strings each, for 3 times 1E12 "check if Hamming distance <= 2" calls. That gets you close to that 4 orders of magnitude.

Tangential: you have to implement your "check if Hamming distance <= 2" call correctly. It shouldn't do "Hamming(s,t) <= 2", but bail out early. Also, you will call it at times where you know the first/middle/last third of characters to be equal, so it should skip those characters (ideally, those shouldn't waste cache line memory at all, but getting there may be too costly in setup time)

New idea: store both sets of strings in tries, iterate over all length 3 prefixes in the first trie, then walk the second one, pruning paths as soon as you hit branches where you know Hamming distance will be larger than two, and peeking in the first trie to check whether pruning is possible. I think that can be made to effectively do what the 'split it 3 parts trick does', but smarter, and may be faster. Implementing it will require some thinking, though, and that thinking may lead to the conclusion that the idea doesn't work.