Near real-time suffix tree construction via the fringe marked ancestor problem

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 [email protected]?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