[issue41972] bytes.find consistently hangs in a particular scenario
Tim Peters
report at bugs.python.org
Mon Oct 19 01:33:18 EDT 2020
Tim Peters <tim at python.org> added the comment:
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.
----------
_______________________________________
Python tracker <report at bugs.python.org>
<https://bugs.python.org/issue41972>
_______________________________________
More information about the Python-bugs-list
mailing list