Suffix Links
Finding extended locus – node to be split - is the hard part
Headi : longest prefix of y(i,n) which is a prefix of y(j,n) for some j<I
Note: if headi-1=az then z is a prefix of headi
Use locus of headi-1 to find locus of headi in stage i
- Use suffix links to go from headi-1 to headi
- In ith tree, only locus of headi does not have a valid suffix link
- In step i, contracted locus of headi in tree i-1 is visited
- Find headi-1=uvw, s.t. uv is the contracted locus of headi-1 in previous tree.
- Rescan: Follow suffix link from this node and then go down path to extended locus of vw
- Scan:continue downward to find extended locus of headi