Another potential algorithm to consider in large needle situations is a Rabin-Karp rolling hash string search.

If used, it's the kind of algorithm that I'd probably bail out to an alternate method on if a run of Rabin-Karp started having a high percentage of false positive failed comparisons (suggesting data antagonistic to the chosen rolling hash algorithm(s) which would degenerate performance back to Needle*Haystack territory).