Tight bounds on the complexity of the Apostolico-Giancarlo algorithm

Abstract : The Apostolico-Giancarlo string-matching algorithm is analyzed precisely. We give a tight upper bound of 3n/2 text characters comparisons when searching for a pattern in a text of length n. We exhibit a family of patterns and texts reaching this bound. We also provide a slightly improved version of the algorithm.
Document type :
Conference papers
Complete list of metadatas

https://hal-upec-upem.archives-ouvertes.fr/hal-00619989
Contributor : Maxime Crochemore <>
Submitted on : Tuesday, March 19, 2013 - 5:23:28 PM
Last modification on : Thursday, May 9, 2019 - 8:02:09 PM
Long-term archiving on : Thursday, June 20, 2013 - 4:21:18 PM

File

lir9612.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00619989, version 1

Citation

Maxime Crochemore, Thierry Lecroq. Tight bounds on the complexity of the Apostolico-Giancarlo algorithm. South American Workshop on String Processing (WSP 1996), 1996, France. pp.64-74. ⟨hal-00619989⟩

Share

Metrics

Record views

286

Files downloads

153