17 Oct
2020
17 Oct
'20
2:32 a.m.
On Fri, 16 Oct 2020 20:24:22 -0500 Tim Peters tim.peters@gmail.com wrote:
Note that no "extra" storage is needed to exploit this. No character lookups, no extra expenses in time or space of any kind. Just "if we mismatch on the k'th try, we can jump ahead k positions".
Ok, so that means that on a N-character haystack, it'll always do at least N character comparisons?
IIRC, the current algorithm is able to do much less than that in favorable cases. If the needle is k characters long and they are all distinct, it's able to do N/k comparisons.
Regards
Antoine.