On 2020年10月16日 20:24:22 -0500 Tim Peters <[email protected]> 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. _______________________________________________ Python-Dev mailing list -- [email protected] To unsubscribe send an email to [email protected] https://mail.python.org/mailman3/lists/python-dev.python.org/ Message archived at https://mail.python.org/archives/list/[email protected]/message/QTB3XVIPZOO3QBVONPWLUN5KHFD3UWBC/ Code of Conduct: http://python.org/psf/codeofconduct/