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
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
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).
How is it quadratic? You do 1000 checks every character in the haystack but that's still O(n)
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...