For every position of S = P$T, measure how far the letters from there agree with the start of S; wherever the whole pattern agrees, it is a match. The trick: an earlier match (the Z-box) already tells you about the letters inside it, so most work is copied rather than redone.
- Average time
- O(n + m)
- Space
- O(n + m)