alt Hacker NewsLooks nice!
One little thing I spotted is you use Boyer Moore Horspool for fast literal search. This is actually not linear in the worst case, although it is almost always sublinear. Worst case would be a literal composed of the same character searching a text of the same character, where it becomes quadratic.
You can actually search strings with character classes using Horspool if you want to, and I have some enhancements to basic Horspool which could maybe help. My library, byteseek [1], implements these.
I also have a much faster algorithm, HashChain [2] which also has a guaranteed linear time version. This was published in the Symposium for Experimental Algorithmics in 2024.
Reading a bit closer, you seem to track how much work is being done in Horspool on each character comparison, and then fall back to the linear KMP if the work budget is exhausted.
This will first massively slow down the Horspool scan, and then once you have done all that work, you rescan it all from the start with KMP if it is doing too much.
One little fix might be to only add to the work counter and compare it outside of the main character comparison loop.
But it would be better to use the linear version of Hashchain. It also uses KMP to make it linear, but it is fully integrated and you would not need to track the work or restart scanning at all. And its a lot faster than Horspool anyway!