I should note that this algorithm is not for untrusted inputs because one can relatively easily fabricate inputs that trigger the worst case (this is even possi

I should note that this algorithm is not for untrusted inputs because one can relatively easily fabricate inputs that trigger the worst case (this is even possible when the attacker can control only the haystack or only the needle). The two-way algorithm, used by glibc and many others, is linear at the worst and cache-friendly enough. Maybe Rabin-Karp is fast enough for short needles even at the worst case; a hybrid algorithm might be interesting (like, two-way algorithm has two variants for long needles and short needles; RK can replace the latter).