On-line construction of suffix trees. (English) Zbl 0831.68027

Summary: An on-line algorithm is presented for constructing the suffix tree for a given string in time linear in the length of the string. The new algorithm has the desirable property of processing the string symbol by symbol from left to right. It always has the suffix tree for the scanned part of the string ready. The method is developed as a linear-time version of a very simple algorithm for (quadratic size) suffix tries. Regardless of its quadratic worst case this latter algorithm can be a good practical method when the string is not too long. Another variation of this method is shown to give, in a natural way, the well-known algorithms for constructing suffix automata (DAWGs).


68P05 Data structures
68W10 Parallel algorithms in computer science
Full Text: DOI


[1] A. Aho and M. Corasick, Efficient string matching: an aid to bibliographic search,Comm. ACM,18 (1975), 333-340. · Zbl 0301.68048
[2] A. Amir and M.Farach, Adaptive dictionary matching,Proc. 32nd IEEE Ann. Symp. on Foundations of Computer Science, 1991, pp. 760-766.
[3] 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. · Zbl 0572.68067
[4] 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. · Zbl 0574.68070
[5] M. Crochemore, Transducers and repetitions,Theoret. Comput. Sci.,45 (1986), 63-86. · Zbl 0615.68053
[6] 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. · Zbl 0659.68109
[7] Z. Galil and R. Giancarlo, Data structures and algorithms for approximate string matching,J. Complexity,4 (1988), 33-72. · Zbl 0646.68078
[8] M. Kempf, R. Bayer, and U. G√ľntzer, Time optimal left to right construction of position trees,Acta Inform.,24 (1987), 461-474. · Zbl 0627.68039
[9] E. McCreight, A space-economical suffix tree construction algorithm,J. Assoc. Comput. Mach.,23 (1976), 262-272. · Zbl 0329.68042
[10] 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.
[11] 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.
[12] E. Ukkonen and D. Wood, Approximate string matching with suffix automata,Algorithmica,10 (1993), 353-364. · Zbl 0779.68038
[13] P. Weiner, Linear pattern matching algorithms,Proc. IEEE 14th Ann. Symp. on Switching and Automata Theory, 1973, pp. 1-11.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.