Bad character
On mismatch at t[i] = c, if c not in pattern, skip |P| chars. Otherwise align rightmost c in pattern.
Advertisement
Good suffix
Suffix of P matched before mismatch. Skip to next occurrence of that suffix (or shorter suffix matching prefix).
Advertisement
Complexity
Best: O(N/M) sublinear. Worst: O(NM). BMH (simplified) — bad char only, popular in practice.
Applications
grep, fgrep. Text editors (find). Any single-pattern search on large text.