Suffix Links: analysis
Rescan:
- resi – shortest suffix of string to be rescanned in step length(resi+!)<=length(resi)-inti
- inti = |resi| - |resi-1|
- length(resn)=0 & length(res0)=n
- Sinti=n – total nodes visited in rescanning
Scan:
- Step i, to find headi, must find z
- scan length(headi)-length(headi-1)+1.
- Totals to n
All other steps are linear.. total time O(n)