Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Tight comparison bounds for the string prefix-matching problem

  • Conference paper
  • First Online:
Combinatorial Pattern Matching (CPM 1993)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 684))

Included in the following conference series:

Abstract

In the string prefix-matching problem one is interested in finding the longest prefix of a pattern string of length m that occurs starting at each position of a text string of length n. This is a natural generalization of the string matching problem where only occurrences of the whole pattern are sought. The Knuth-Morris-Pratt string matching algorithm can be easily adapted to solve the string prefix-matching problem without making additional comparisons.

In this paper we study the exact complexity of the string prefix-matching problem in the deterministic sequential comparison model. Our bounds do not account for comparisons made in a pattern preprocessing step. The following results are presented:

  1. 1.

    A family of linear-time string prefix-matching algorithms that make at most [2m−1/m n] comparisons

  2. 2.

    A tight lower bound of [2m−1/m n] comparisons for any string prefix-matching algorithm. We also consider the special case when the pattern and the text strings are the same string and all comparisons are accounted. This problem, which we call the string self-prefix problem, is similar to the failure function that is computed in the pattern preprocessing of the Knuth-Morris-Pratt string matching algorithm and used in several other comparison efficient algorithms. By using the lower bound for the siring prefix-matching problem we are able to show:

  3. 3.

    A lower bound of 2m−[2√m] comparisons for the self-prefix problem.

Partially supported by the European Research Consortium for Informatics and Mathematics postdoctoral fellowship.

Partially supported by “Progetto Finalizzato Sistemi Informatici e Calcolo Parallelo” of CNR under grant number 89.00026.69.

This work was done while this author was visiting at the Department of Computer Science in Columbia University.

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

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. A. V. Aho, J. E. Hopcroft, and J. D. Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading, MA, 1974.

    Google Scholar 

  2. R. S. Boyer and J. S. Moore. A fast string searching algorithm. Comm. of the ACM, 20:762–772, 1977.

    Google Scholar 

  3. D. Breslauer, L. Colussi, and L. Toniolo. On the Exact Complexity of the String Prefix-Matching Problem. In preparation, 1993.

    Google Scholar 

  4. D. Breslauer and Z. Galil. Efficient Comparison Based String Matching. J. Complexity, 1993. To appear.

    Google Scholar 

  5. R. Cole and R. Hariharan. Tighter Bounds on The Exact Complexity of String Matching. In Proc. 33rd IEEE Symp. on Foundations of Computer Science, pages 600–609, 1992.

    Google Scholar 

  6. L. Colussi. Correctness and efficiency of string matching algorithms. Inform. and Control, 95:225–251, 1991.

    Google Scholar 

  7. Z. Galil and R. Giancarlo. On the exact complexity of string matching: lower bounds. SIAM J. Comput., 20(6):1008–1020, 1991.

    Google Scholar 

  8. Z. Galil and R. Giancarlo. The exact complexity of string matching: upper bounds. SIAM J. Comput., 21(3):407–437, 1992.

    Google Scholar 

  9. D. E. Knuth, J. H. Morris, and V. R. Pratt. Fast pattern matching in strings. SIAM J. Comput., 6:322–350, 1977.

    Google Scholar 

  10. U. Zwick and M. S. Paterson. Lower bounds for string matching in the sequential comparison model. Manuscript, 1991.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Centrum voor Wiskunde eu Informatica, P.O. Box 4079, 1009, AB Amsterdam, The Netherlands

    Dany Breslauer

  2. Dipartimento di Matematica Pura ed Applicata, Universitá di Padova, Via Belzoni 7, 35131, Padova, Italy

    Livio Colussi & Laura Toniolo

Authors
  1. Dany Breslauer
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Livio Colussi
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Laura Toniolo
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Alberto Apostolico Maxime Crochemore Zvi Galil Udi Manber

Rights and permissions

Reprints and permissions

Copyright information

© 1993 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Breslauer, D., Colussi, L., Toniolo, L. (1993). Tight comparison bounds for the string prefix-matching problem. In: Apostolico, A., Crochemore, M., Galil, Z., Manber, U. (eds) Combinatorial Pattern Matching. CPM 1993. Lecture Notes in Computer Science, vol 684. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0029793

Download citation

  • DOI: https://doi.org/10.1007/BFb0029793

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-56764-6

  • Online ISBN: 978-3-540-47732-7

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation