T: aaaaaaaaaaaa
P: xaaaaa
Not easy to come up with an improvement, there will always be that exception you didn't think of XD
I wonder, if you could derive meta information about the DNA "lyrical" composition by observing the BM put through. After all the algorithm assumes random text.
I haven't recently looked into the sub-quadratic worst case improved version of BM, but IIRC it's far from trivial and not what most people think of for this algorithm. I assume it's also slower IRL, for cache misses, or for expensive operations like modulo in the main loop, and prolly has a space penalty.
BM just has a better average case than naive string search.