[Python-Dev] Re: Changing Python's string search algorithms

[Dennis Sweeney <sweeney.dennis650@gmail.com>]

Here's my attempt at some heuristic motivation:

Thanks, Dennis! It helps. One gloss:

.... 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.

The amazing (to me) thing is that splitting into JUST two parts is always enough to guarantee linearity. What if there are a million different patterns going on ? Doesn't matter! I assume this remarkable outcome is a consequence of the Critical Factorization Theorem.