Data structures and algorithms for the string statistics problem. (English) Zbl 0846.68023

Summary: Given a textstring \(x\) of length \(n\), the minimal augmented suffix tree \(\widehat T(x)\) of \(x\) is a digital-search index that returns, for any query string \(w\) and in a number of comparisons bounded by the length of \(w\), the maximum number of nonoverlapping occurrences of \(w\) in \(x\). It is shown that, denoting the length of \(x\) by \(n\), \(\widehat T(x)\) can be built in time \(O(n\log^2 n)\) and space \(O(n\log n)\), off-line on a RAM.


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


[1] A. V. Aho, J. E. Hopcroft, and J. D. Ullman,The Design and Analysis of Computer Algorithms, Addison-Wesley, Reading, MA, 1974. · Zbl 0326.68005
[2] A. Apostolico, The myriad virtues of subword trees, inCombinatorial Algorithms on Words (A. Apostolico and Z. Galil, eds.), ASI F-12, Springer-Verlag, New York, pp. 85–95, 1985. · Zbl 0572.68067
[3] A. Apostolico and F. P. Preparata, Optimal off-line detection of repetitions in a string,Theoret. Comput. Sci.,22 (1983), pp. 297–515. · Zbl 0497.68052
[4] A. Apostolico and F. P. Preparata, Structural properties of the string statistics problem,J. Comput. System Sci.,31(3) (1985), 394–411. · Zbl 0593.68047
[5] M. Crochemore and W. Rytter, Squares, cubes, and time-space efficient string searching,Algorithmica,13 (1995), 405–425. · Zbl 0849.68044
[6] R. C. Lyndon and M. P. Schutzenberger, The equationa M =b N c P in a free group,Michigan Math. J.,9 (1962), 289–298. · Zbl 0106.02204
[7] E. M. McCreight, A space economical suffix tree construction algorithm,J. Assoc. Comput. Mach.,25 (1976), 262–272. · Zbl 0329.68042
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.