On Fri, 16 Oct 2020 20:24:22 -0500 Tim Peters <tim.pet...@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. _______________________________________________ Python-Dev mailing list -- python-dev@python.org To unsubscribe send an email to python-dev-le...@python.org https://mail.python.org/mailman3/lists/python-dev.python.org/ Message archived at https://mail.python.org/archives/list/python-dev@python.org/message/QTB3XVIPZOO3QBVONPWLUN5KHFD3UWBC/ Code of Conduct: http://python.org/psf/codeofconduct/
