Start of ass1

1 files changed, 30 insertions, 0 deletions

diff --git a/w2/w2lect.md b/w2/w2lect.md
new file mode 100644
index 0000000..3fee16a
--- /dev/null
+++ b/w2/w2lect.md
@@ -0,0 +1,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)