摘要: An on-line algorithm is presented for constructing the suffix tree a given string in time linear length of string. The new has desirable property processing symbol by from left to right. It always scanned part ready. method developed as linear-time version very simple (quadratic size) suffixtries. Regardless its quadratic worst case this latter can be good practical when not too long. Another variation shown give, natural way, well-known algorithms automata (DAWGs).
springer.com
acm.org
stanford.edu 
sci-hub.se 参考文章(13)
Alberto Apostolico, The Myriad Virtues of Subword Trees Springer, Berlin, Heidelberg. pp. 85- 96 ,(1985) , 10.1007/978-3-642-82456-2_6
Esko Ukkonen, Constructing Suffix Trees On-Line in Linear Time world computer congress on algorithms software architecture. pp. 484- 492 ,(1992)
Maxime Crochemore, String matching with constraints Lecture Notes in Computer Science. pp. 44- 58 ,(1988) , 10.1007/BFB0017130
Esko Ukkonen, Approximate String-Matching over Suffix Trees combinatorial pattern matching. pp. 228- 242 ,(1993) , 10.1007/BFB0029808
A. Blumer, J. Blumer, D. Haussler, A. Ehrenfeucht, M.T. Chen, J. Seiferas, THE SMALLEST AUTOMATON RECOGNIZING THE SUBWORDS OF A TEXT Theoretical Computer Science. ,vol. 40, pp. 31- 55 ,(1985) , 10.1016/0304-3975(85)90157-4
Z Galil, R Giancarlo, Data structures and algorithms for approximate string matching Journal of Complexity. ,vol. 4, pp. 33- 72 ,(1988) , 10.1016/0885-064X(88)90008-8
Esko Ukkonen, Derick Wood, Approximate string matching with suffix automata Algorithmica. ,vol. 10, pp. 353- 364 ,(1993) , 10.1007/BF01769703
M. Kempf, R. Bayer, U. G�ntzer, Time optimal left to right construction of position trees Acta Informatica. ,vol. 24, pp. 461- 474 ,(1987) , 10.1007/BF00292114
Alfred V. Aho, Margaret J. Corasick, Efficient string matching: an aid to bibliographic search Communications of The ACM. ,vol. 18, pp. 333- 340 ,(1975) , 10.1145/360825.360855
Edward M. McCreight, A Space-Economical Suffix Tree Construction Algorithm Journal of the ACM. ,vol. 23, pp. 262- 272 ,(1976) , 10.1145/321941.321946