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!