Search 'ABAB' in 'ABABABAB' with KMP: prefix function for pattern is [0,0,1,2]. Match ABAB at 0-3; on mismatch at position 4, instead of restarting, the prefix table shifts the pattern by 2 (overlap 'AB'), continuing in O(n). Naive would recheck from position 1.