COURSE III · CHAMPIONSHIP · VERSION 2
Advanced trees and string matching
Measurable outcome: Decompose a tree problem, recognize when offline preprocessing is useful, and implement one linear-time string matcher.
Concept checklist
- Euler tours and subtree intervals
- Binary lifting and lowest common ancestors
- KMP prefix function and border reasoning
- Aho–Corasick as trie plus failure links
Implementation lab
- Flatten a rooted tree and answer subtree queries.
- Implement binary lifting with an explicit sentinel policy.
- Implement prefix-function matching and test periodic strings.
Mapped problems
Exit criteria
- Explain the key invariant without notes.
- Reimplement the core technique in one sitting.
- Solve two mapped tasks without editorial help.
- Record one mistake and the test that exposes it.