Movatterモバイル変換

[0]ホーム
URL:

Skip to main content

Advertisement

Springer Nature Link
Log in

On-Line Construction of Parameterized Suffix Trees

  • Conference paper

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

Abstract

We consider on-line construction of a suffix tree for a parameterized string, where we always have the suffix tree of the input string read so far. This situation often arises from source code management systems where, for example, a source code repository is gradually increasing in its size as users commit new codes into the repository day by day. We present an on-line algorithm which constructs a parameterized suffix tree in randomizedO(n) time, wheren is the length of the input string. Our algorithm is the first randomized linear time algorithm for the on-line construction problem.

This work was supported by Korea Research Council of Fundamental Science and Technology. The ICT at Seoul National University provides research facilities for this study.

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. Baker, B.S.: A theory of parameterized pattern matching: algorithms and applications. In: STOC 1993: Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, pp. 71–80. ACM, New York (1993)

    Chapter  Google Scholar 

  2. Baker, B.S.: Parameterized duplication in strings: Algorithms and an application to software maintenance. SIAM J. Comput. 26(5), 1343–1362 (1997)

    Article MathSciNet MATH  Google Scholar 

  3. Shibuya, T.: Generalization of a suffix tree for RNA structural pattern matching. Algorithmica 39(1), 1–19 (2004)

    Article MathSciNet MATH  Google Scholar 

  4. Weiner, P.: Linear pattern matching algorithms. In: SWAT 1973: Proceedings of the 14th Annual Symposium on Switching and Automata Theory, Washington, DC, USA, pp. 1–11. IEEE Computer Society, Los Alamitos (1973)

    Google Scholar 

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

    Article MathSciNet MATH  Google Scholar 

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

    Article MathSciNet MATH  Google Scholar 

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

    Article MathSciNet MATH  Google Scholar 

  8. Rao Kosaraju, S.: Faster algorithms for the construction of parameterized suffix trees. In: FOCS 1995: Proceedings of the 36th Annual Symposium on Foundations of Computer Science, pp. 631–637. IEEE Computer Society, Los Alamitos (1995)

    Google Scholar 

  9. Cole, R., Hariharan, R.: Faster suffix tree construction with missing suffix links. SIAM J. Comput. 33(1), 26–42 (2004)

    Article MathSciNet MATH  Google Scholar 

  10. Giancarlo, R.: A generalization of the suffix tree to square matrices, with applications. SIAM J. Comput. 24(3), 520–562 (1995)

    Article MathSciNet MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. School of Computer Science and Engineering, Seoul National University, Seoul, 151-742, South Korea

    Taehyung Lee & Kunsoo Park

  2. Department of Computer Science and Engineering, Sejong University, Seoul, 143-747, South Korea

    Joong Chae Na

Authors
  1. Taehyung Lee

    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. Kunsoo Park

    You can also search for this author inPubMed Google Scholar

Editor information

Editors and Affiliations

  1. Swedish Institute of Computer Science, Kista, Sweden

    Jussi Karlgren

  2. Department of Computer Science and Engineering, Helsinki University of Technology, P.O. Box 5400, 02015 HUT, Espoo, Finland

    Jorma Tarhio

  3. Department of Computer Sciences, University of Tampere, Tampere, Finland

    Heikki Hyyrö

Rights and permissions

Copyright information

© 2009 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Lee, T., Na, J.C., Park, K. (2009). On-Line Construction of Parameterized Suffix Trees . In: Karlgren, J., Tarhio, J., Hyyrö, H. (eds) String Processing and Information Retrieval. SPIRE 2009. Lecture Notes in Computer Science, vol 5721. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-03784-9_4

Download citation

Publish with us

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