Here's my attempt at some heuristic motivation:
Try to construct a needle that will perform as poorly as possible when
using the naive two-nested-for-loops algorithm. You'll find that if
there isn't some sort of vague periodicity in your needle, then you
won't ever get *that* unlucky; each particular alignment will fail
early, and if it doesn't then some future alignment would be pigeonholed
to fail early.
So Crochemore and Perrin's algorithm explicitly handles this "worst case"
of periodic strings. Once we've identified in the haystack some period
from the needle, there's no need to re-match it. We can keep a memory
of how many periods we currently remember matching up, and never re-match
them. This is what gives the O(n) behavior for periodic strings.
But wait! There are some bad needles that aren't quite periodic.
For instance:
>>> 'ABCABCAABCABC' in 'ABC'*1_000_000
The key insight though is that the worst strings are still
"periodic enough", and if we have two different patterns going on,
then we can intentionally split them apart. For example,
`"xyxyxyxyabcabc" --> "xyxyxyxy" + "abcabc"`. I believe the goal is to
line it up so that if the right half matches but not the left then we
can be sure to skip somewhat far ahead. This might not correspond
exactly with splitting up two patterns. This is glossing over some
details that I'm admittedly still a little hazy on as well, but
hopefully that gives at least a nudge of intuition.
_______________________________________________
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/MXMS5XIV6WJFFRHTH7TBHAO3TC4QIHBZ/
Code of Conduct: http://python.org/psf/codeofconduct/
