Compare from the right end of the pattern, and use what failed to slide it as far as it can safely go.
This interactive visualization needs JavaScript.