What about the worst case? I.e. something like searching for 1000 'a's in a long string of 'a's interspersed with 'b's every 500-1000 steps? Seems accidentally quadradic unfortunately in the absence of some KMP-like fallback

▲

MattPalmer1086 5 days ago | parent | next [-]

Worst case for these types of search is O(mn), m length of needle, n length of haystack. It is not linear in n.

The absolute worst case is when both the needle and haystack are both composed of the same byte repeated (e.g. all zero).

▲

expenses3 5 days ago | parent | prev [-]

How is it quadratic? You do 1000 checks every character in the haystack but that's still O(n)

	▲	burntsushi 5 days ago \| parent [-]
		The worst case is that `std.mem.eql`[1] is executed at every position in the haystack, which gives you `O(n*m)` time complexity. Several substring search algorithms are `O(n)`. [1]: https://github.com/aarol/substr/blob/9392f9557de735929dfb79e...