# Boyer-Moore

## Bad character rule:

Shift pattern along to the left to the right-most version of the bad character
$O(m+n)$ *mostly*

## Extended bad character rule
- 2D array for each char and each position in the pattern
- **Reduces naive shifts (i.e. by 1 to the right) but takes more space**
	- Could use linked lists or something but that takes more time

## Good suffix rule
**Makes Boyer-Moore worst case *almost* linear time rather than squared time**
- A suffix before the bad character that you know matches the text
- character to the left of the next instance of the good suffix must be different to the one to the left of the original suffix
- Move pattern along to the right to the point where the next suffix in the pattern matches

## Galil's optimization
Improves on good suffix rules
**Actually linear time**
extended just makes it slightly faster and doesn't change the complexity

# KNP
- $O(m+n)$
- Easier to write, simpler
- Slower in practise than Boyer-Moore
- If mismatched first charatcer, move left by 1 (not covered by slides)
- Use Galil's on this too
- Proof is examinable (BM isn't)