Week 9: String Algorithms, Approximation (19)

When a mismatch occurs between P[j] and T[i+j], shift the pattern all the way to align P[0] with T[i+j]

⇒ each character in T checked at most twice

Example:

abcdabcdeabcc abcdabcdeabcc
abcdexxxxxxxx xxxxabcde