On the Comparison Complexity of the String Prefix-Matching Problem

Forfattere

  • Dany Breslauer
  • Livio Colussi
  • Laura Toniolo

DOI:

https://doi.org/10.7146/brics.v2i46.19947

Resumé

In this paper we study the exact comparison complexity of the string
prefix-matching problem in the deterministic sequential comparison model
with equality tests. We derive almost tight lower and upper bounds on
the number of symbol comparisons required in the worst case by on-line
prefix-matching algorithms for any fixed pattern and variable text. Unlike
previous results on the comparison complexity of string-matching and
prefix-matching algorithms, our bounds are almost tight for any particular pattern.
We also consider the special case where the pattern and the text are the
same string. This problem, which we call the string self-prefix problem, is
similar to the pattern preprocessing step of the Knuth-Morris-Pratt string-matching
algorithm that is used in several comparison efficient string-matching
and prefix-matching algorithms, including in our new algorithm.
We obtain roughly tight lower and upper bounds on the number of symbol
comparisons required in the worst case by on-line self-prefix algorithms.
Our algorithms can be implemented in linear time and space in the
standard uniform-cost random-access-machine model.

Downloads

Publiceret

1995-06-16

Citation/Eksport

Breslauer, D., Colussi, L., & Toniolo, L. (1995). On the Comparison Complexity of the String Prefix-Matching Problem. BRICS Report Series, 2(46). https://doi.org/10.7146/brics.v2i46.19947

Nummer

Nr. 46 (1995): RS-46 On the Comparison Complexity of the String Prefix-Matching Problem

Sektion

Artikler

Licens

Authors who publish with this journal agree to the following terms:

    1. Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.

    1. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.

  1. Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).