This issue tracker has been migrated to GitHub, and is currently read-only.
For more information, see the GitHub FAQs in the Python's Developer Guide.

Author tim.peters
Recipients Dennis Sweeney, Zeturic, ammar2, corona10, gregory.p.smith, gvanrossum, josh.r, pmpp, serhiy.storchaka, tim.peters, vstinner
Date 2020-10-19.05:33:18
SpamBayes Score -1.0
Marked as misclassified Yes
Message-id <1603085598.85.0.395958635203.issue41972@roundup.psfhosted.org>
In-reply-to
Content
I confess I _assumed_ all along that you were generalizing the current code's Sunday trick to 7-bit equivalence classes (up from 32 bits total) and 64K possible shift counts (up from just 2 total possibilities: 1 or len(needle)+1). The Sunday trick couldn't care less where or when the mismatch occurs, just that a mismatch occurred somewhere.

In my head I was picturing the paper's code, not the PR.  Whenever it makes a shift, it could compare it to the "Sunday-ish shift", and pick the larger.  That should have no effect on worst case O() behavior - it would always shift at least as much as Crochempre-Perrin when a mismatch was hit.

I can't say how it would relate to details of the PR's spelling, because I'm still trying to fully understand the paper ;-) I don't believe I can usefully review the code before then.
History
Date User Action Args
2020-10-19 05:33:18tim.peterssetrecipients: + tim.peters, gvanrossum, gregory.p.smith, vstinner, pmpp, serhiy.storchaka, josh.r, ammar2, corona10, Dennis Sweeney, Zeturic
2020-10-19 05:33:18tim.peterssetmessageid: <1603085598.85.0.395958635203.issue41972@roundup.psfhosted.org>
2020-10-19 05:33:18tim.peterslinkissue41972 messages
2020-10-19 05:33:18tim.peterscreate