Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
430893 | Journal of Discrete Algorithms | 2013 | 17 Pages |
Abstract
We contribute a further step towards the plausible real-time construction of suffix trees by presenting an on-line algorithm that spends only O(loglogn) time processing each input symbol and takes O(nloglogn) time in total, where n is the length of the input text. Our results improve on a previously published algorithm that takes O(logn) time per symbol and O(nlogn) time in total. The improvements are obtained by adapting Weinerʼs suffix tree construction algorithm to use a new data structure for the fringe marked ancestor problem, a special case of the nearest marked ancestor problem, which may be of independent interest.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Dany Breslauer, Giuseppe F. Italiano,