CLR cover
Previous problem

Problem 55: Bare Suffix Tree

Next problem

Suffix trees provide a data structure for indexing texts. Optimal-time constructions of them suffer from a rather high memory requirement, larger than for Suffix arrays with the same usage. The problem deals with a moderately efficient but not completely naive and very simple construction of Suffix trees.

The Suffix tree of a word ending with a unique end marker is the compacted trie of suffixes of . A leaf corresponds to a suffix and an internal node to a factor having at least two occurrences followed by different letters. Each edge is labelled by a factor of , represented by the pair . Its word-length is . The word-length of a path in is the sum of word-lengths of its edges, while the length of the path is its number of edges. Let be the maximum length of a path in from the root to a leaf. Let be the leaf ending the branch labelled by .

Design a construction of the Suffix tree of a word using no additional array and running in time on a fixed-size alphabet.

References

  • E. M. McCreight. A space-economical suffix tree construction algorithm. J. ACM, 23(2):262-272, 1976.
  • E. Ukkonen. On-line construction of suffix trees. Algorithmica, 14(3):249-260, 1995.