17 Oct
2020
17 Oct
'20
9:32 a.m.
On Fri, 16 Oct 2020 20:24:22 -0500
Tim Peters
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.