Message378924
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. |
|
Date |
User |
Action |
Args |
2020-10-19 05:33:18 | tim.peters | set | recipients:
+ tim.peters, gvanrossum, gregory.p.smith, vstinner, pmpp, serhiy.storchaka, josh.r, ammar2, corona10, Dennis Sweeney, Zeturic |
2020-10-19 05:33:18 | tim.peters | set | messageid: <1603085598.85.0.395958635203.issue41972@roundup.psfhosted.org> |
2020-10-19 05:33:18 | tim.peters | link | issue41972 messages |
2020-10-19 05:33:18 | tim.peters | create | |
|