Movatterモバイル変換

[0]ホーム
URL:

Skip to main content

Advertisement

Springer Nature Link
Log in

A Simple Construction of Two-Dimensional Suffix Trees in Linear Time

(Extended Abstract)

  • Conference paper

Part of the book series:Lecture Notes in Computer Science ((LNTCS,volume 4580))

Included in the following conference series:

  • 785Accesses

Abstract

The two-dimensional suffix tree of a matrixA is a compacted trie that represents all square submatrices ofA. There exists a linear-time construction of two-dimensional suffix trees using theodd-even scheme. This algorithm has the drawback that the merging step is quite complicated. In this paper, we propose a new and simple algorithm to construct two-dimensional suffix trees in linear time by applying theskew scheme to square matrices. To do this, we present a simple algorithm to merge two Isuffix trees in linear time.

This is a preview of subscription content,log in via an institution to check access.

Access this chapter

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Amir, A., Farach, M.: Two-dimensional dictionary matching. IPL 21, 233–239 (1992)

    Article MathSciNet  Google Scholar 

  2. Apostolico, A.: The myriad virtues of subword trees. In: Apostolico, A., Galil, Z. (eds.) Combinatorial Algorithms on Words, pp. 85–95. Springer, Heidelberg (1985)

    Google Scholar 

  3. Chen, M.T., Seiferas, J.: Efficient and elegant subword tree construction. In: Apostolico, A., Galil, Z. (eds.) Combinatorial Algorithms on Words, F. NATO Advanced Science Institutes, vol. 12, pp. 97–107. Springer, Heidelberg (1985)

    Google Scholar 

  4. Cole, R., Hariharan, R.: Faster suffix tree construction with missing suffix links. In: Proc. of the 30th STOC, pp. 407–415 (2000)

    Google Scholar 

  5. Crochemore, M., Rytter, W.: Jewels of Stringology. World Scientific Publishing, Singapore (2002)

    Google Scholar 

  6. Farach, M.: Optimal suffix tree construction with large alphabets. In: Proc. of the 38th FOCS, pp. 137–143 (1997)

    Google Scholar 

  7. Farach, M., Muthukrishnan, S.: Optimal logarithmic time randomized suffix tree construction. In: Proc. of the 23rd ICALP, pp. 550–561 (1996)

    Google Scholar 

  8. Farach-Colton, M., Ferragina, P., Muthukrishnan, S.: On the sorting-complexity of suffix tree construction. J. ACM 47(6), 987–1011 (2000)

    Article MATH MathSciNet  Google Scholar 

  9. Giancarlo, R.: A generalization of the suffix tree to square matrices, with application. SIAM J. on Comp. 24(3), 520–562 (1995)

    Article MATH MathSciNet  Google Scholar 

  10. Giancarlo, R., Grossi, R.: On the construction of classes of suffix trees for square matrices: Algorithms and applications. Information and Computation 130(2), 151–182 (1996)

    Article MATH MathSciNet  Google Scholar 

  11. Giancarlo, R., Grossi, R.: Suffix tree data structures for matrices. In: Apostolico, A., Galil, Z. (eds.) Pattern Matching Algorithms, chapter 11, pp. 293–340. Oxford University Press, Oxford (1997)

    Google Scholar 

  12. Giancarlo, R., Guaiana, D.: On-line construction of two-dimensional suffix trees. Journal of Complexity 15(1), 72–127 (1999)

    Article MATH MathSciNet  Google Scholar 

  13. Gonnet, G.H.: Efficient searching of text and pictures. Technical Report OED-88-02, University of Waterloo (1988)

    Google Scholar 

  14. Gusfield, D.: Algorithms on Strings, Tree, and Sequences. Cambridge University Press, Cambridge (1997)

    Google Scholar 

  15. Harel, D., Tarjan, R.: Fast algorithms for finding nearest common ancestors. SIAM J. on Comp. 13(2), 338–355 (1984)

    Article MATH MathSciNet  Google Scholar 

  16. Hariharan, R.: Optimal parallel suffix tree construction. In: Proc. of the 26th FOCS, pp. 290–299 (1994)

    Google Scholar 

  17. Hon, W.K., Sadakane, K., Sung, W.K.: Breaking a time-and-space barrier in constructing full-text indices. In: Proc. of the 44th FOCS, pp. 251–260 (2003)

    Google Scholar 

  18. Kärkkäinen, J., Sanders, P., Burkhardt, S.: Linear work suffix array construction. J. ACM (in press)

    Google Scholar 

  19. Kim, D.K., Kim, Y.A., Park, K.: Generalizations of suffix arrays to multi-dimensional matrices. TCS 302(1-3), 401–416 (2003)

    Article MATH  Google Scholar 

  20. Kim, D.K., Park, K.: Linear-time construction of two-dimensional suffix trees. In: Proc. of the 26th ICALP, pp. 463–372 (1999)

    Google Scholar 

  21. Kim, D.K., Sim, J.S., Park, H., Park, K.: Constructing suffix arrays in linear time. J. Disc. Alg. 3(2-4), 126–142 (2005)

    Article MATH MathSciNet  Google Scholar 

  22. Ko, P., Aluru, S.: Space efficient linear time construction of suffix arrays. J. Disc. Alg. 3(2-4), 143–156 (2005)

    Article MATH MathSciNet  Google Scholar 

  23. Manber, U., Myers, G.: Suffix arrays: A new method for on-line string searches. SIAM J. on Comp. 22(5), 935–948 (1993)

    Article MATH MathSciNet  Google Scholar 

  24. McCreight, E.M.: A space-economical suffix tree construction algorithms. J. ACM 23(2), 262–272 (1976)

    Article MATH MathSciNet  Google Scholar 

  25. Na, J.C., Giancarlo, R., Park, K.: O(n2logn) time on-line construction of two-dimensional suffix trees. In: Proc. of the 11th COCOON, pp. 273–282 (2005)

    Google Scholar 

  26. Sahinalp, S.C., Vishkin, U.: Symmetry breaking for suffix tree construction. In: Proc. of the 26th FOCS, pp. 300–309 (1994)

    Google Scholar 

  27. Schieber, B., Vishkin, U.: On finding lowest common ancestors: Simplification and parallelization. SIAM J. on Comp. 17(6), 1253–1262 (1988)

    Article MATH MathSciNet  Google Scholar 

  28. Ukkonen, E.: On-line construction of suffix trees. Algorithmica 14(3), 249–260 (1995)

    Article MATH MathSciNet  Google Scholar 

  29. Weiner, P.: Linear pattern matching algorithms. In: Proc. of the 14th IEEE Symp. on Switching and Automata Theory, pp. 1–11 (1973)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Division of Electronics and Computer Engineering, Hanyang University, Korea

    Dong Kyue Kim

  2. Department of Advanced Technology Fusion, Konkuk University, Korea

    Joong Chae Na

  3. School of Computer Science and Engineering, Inha University, Korea

    Jeong Seop Sim

  4. School of Computer Science and Engineering, Seoul National University, Korea

    Kunsoo Park

Authors
  1. Dong Kyue Kim

    You can also search for this author inPubMed Google Scholar

  2. Joong Chae Na

    You can also search for this author inPubMed Google Scholar

  3. Jeong Seop Sim

    You can also search for this author inPubMed Google Scholar

  4. Kunsoo Park

    You can also search for this author inPubMed Google Scholar

Editor information

Bin Ma Kaizhong Zhang

Rights and permissions

Copyright information

© 2007 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Kim, D.K., Na, J.C., Sim, J.S., Park, K. (2007). A Simple Construction of Two-Dimensional Suffix Trees in Linear Time. In: Ma, B., Zhang, K. (eds) Combinatorial Pattern Matching. CPM 2007. Lecture Notes in Computer Science, vol 4580. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-73437-6_35

Download citation

Publish with us

[8]ページ先頭
©2009-2025 Movatter.jp