Fixes
Must get suffix links pointing to the right place
Fix them up as we go along – lazy or eager
eager: keep track of min - node of shortest length with a bad pointer pointing to N
Six phases:
- Set temporary suffix link for previous head
- Scan headi
- Add new internal node if needed
- call update to fix suffix links and min pointers
- Fix min pointers of headi-1
- Create new node with appropriate suffix
- update oldhd and oldchild pointers
O(n(|? |+log(| ? |+|S )))), improve to O(n logn): concatenable queues & dynamic trees.