blob: 3fee16aa028bfb470029755e31da8ab353212121 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
# 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)
|
