| Article ID: | iaor20117047 |
| Volume: | 37 |
| Issue: | 1 |
| Start Page Number: | 43 |
| End Page Number: | 74 |
| Publication Date: | Sep 2003 |
| Journal: | Algorithmica |
| Authors: | Maa |
| Keywords: | trees |
Affix trees are a generalization of suffix trees that are based on the inherent duality of suffix trees induced by the suffix links. An algorithm is presented that constructs affix trees on‐line by expanding the underlying string in both directions and that is the first known algorithm to do this with linear time complexity.