3 ms·
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
by lokeg 1y ago
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
- expenses3 1y agoHow is it quadratic? You do 1000 checks every character in the haystack but that's still O(n)
- burntsushi 1y agoThe 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/9392f9557de735929dfb79efa4fc88115341c65d/src/main.zig#L82 https://github.com/aarol/substr/blob/9392f9557de735929dfb79e...
- MattPalmer1086 1y agoWorst 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).