On-line construction of suffix trees

A. Aho and M. Corasick, Efficient string matching: an aid to bibliographic search,Comm. ACM,18 (1975), 333?340.

A. Amir and M.Farach, Adaptive dictionary matching,Proc. 32nd IEEE Ann. Symp. on Foundations of Computer Science, 1991, pp. 760?766.

A. Apostolico, The myriad virtues of subword trees, inCombinatorial Algorithms on Words (A. Apostolico and Z. Galil, eds.), Springer-Verlag, New York, 1985, pp. 85?95.

A. Blumer, J. Blumer, D. Haussier, A. Ehrenfeucht, M. T. Chen, and J. Seiferas, The smallest automaton recognizing the subwords of a text,Theoret. Comput. Sci.,40 (1985), 31?55.

M. Crochemore, Transducers and repetitions,Theoret. Comput. Sci.,45 (1986), 63?86.

M. Crochemore, String matching with constraints, inMathematical Foundations of Computer Science 1988 (M. P. Chytil, L. Janiga and V. Koubek, eds.), Lecture Notes in Computer Science, vol. 324, Springer-Verlag, Berlin, 1988, pp. 44?58.

Z. Galil and R. Giancarlo, Data structures and algorithms for approximate string matching,J. Complexity,4 (1988), 33?72.

M. Kempf, R. Bayer, and U. Güntzer, Time optimal left to right construction of position trees,Acta Inform.,24 (1987), 461?474.

E. McCreight, A space-economical suffix tree construction algorithm,J. Assoc. Comput. Mach.,23 (1976), 262?272.

E. Ukkonen, Constructing suffix trees on-line in linear time, inAlgorithms, Software, Architecture. Information Processing 92, vol. I (J. van Leeuwen, ed.), Elsevier, Amsterdam, 1992, pp. 484?492.

E. Ukkonen, Approximate string-matching over suffix trees, inCombinatorial Pattern Matching, CPM '93 (A. Apostolico, M. Crochemore, Z. Galil, and U. Manber, eds.), Lecture Notes in Computer Science, vol. 684, Springer-Verlag, Berlin 1993, pp. 228?242.

E. Ukkonen and D. Wood, Approximate string matching with suffix automata,Algorithmica,10 (1993), 353?364.

P. Weiner, Linear pattern matching algorithms,Proc. IEEE 14th Ann. Symp. on Switching and Automata Theory, 1973, pp. 1?11.