CLR cover
Previous problem

Problem 47: Suffix Array to the Suffix Tree

Next problem

The goal of the problem is to transform the Suffix array of a word $x$ into its Suffix tree. Despite the fact that both data structures infer essentially the same types of indexing operations, some come more readily from the Suffix tree structure.

The interest in designing a linear-time algorithm to do it is interesting when the alphabet is linearly sortable. Indeed, with this hypothesis, there are many linear-time algorithms to build the Suffix array of a word, although there is mostly one method to build its Suffix tree in the same time. Moreover, techniques used for the former construction are way easier to develop.

Show how to build the Suffix tree of a word in linear time given its Suffix array.

References

  • M. Crochemore, C. Hancart, and T. Lecroq. Algorithms on Strings. Cambridge University Press, 2007. 392 pages.
  • M. Farach. Optimal suffix tree construction with large alphabets. In 38th Annual Symposium on Foundations of Computer Science, FOCS '97, Miami Beach, Florida, USA, October 19-22, 1997, pages 137-143. IEEE Computer Society, 1997.
  • J. Kärkkäinen and P. Sanders. Simple linear work suffix array construction. In J. C. M. Baeten, J. K. Lenstra, J. Parrow, and G. J. Woeginger, editors, Automata, Languages and Programming, 30th International Colloquium, ICALP 2003, Eindhoven, The Netherlands, June 30 - July 4, 2003. Proceedings, volume 2719 of Lecture Notes in Computer Science, pages 943-955. Springer, 2003.
  • J. Kärkkäinen, P. Sanders, and S. Burkhardt. Linear work suffix array construction. J. ACM, 53(6):918-936, 2006.
  • D. K. Kim, J. S. Sim, H. Park, and K. Park. Constructing suffix arrays in linear time. J. Discrete Algorithms, 3(2-4):126-142, 2005.
  • P. Ko and S. Aluru. Space efficient linear time construction of suffix arrays. J. Discrete Algorithms, 3(2-4):143-156, 2005.