Skip to Main content Skip to Navigation
Journal articles

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 character 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 :
Journal articles
Complete list of metadatas

https://hal-upec-upem.archives-ouvertes.fr/hal-00619574
Contributor : Maxime Crochemore <>
Submitted on : Tuesday, March 19, 2013 - 5:19:40 PM
Last modification on : Wednesday, February 26, 2020 - 7:06:05 PM
Document(s) archivé(s) le : Thursday, June 20, 2013 - 4:21:04 PM

File

ipl2.pdf
Files produced by the author(s)

Identifiers

Citation

Maxime Crochemore, Thierry Lecroq. Tight bounds on the complexity of the Apostolico-Giancarlo algorithm. Information Processing Letters, Elsevier, 1997, 63 (4), pp.195-203. ⟨10.1016/S0020-0190(97)00107-5⟩. ⟨hal-00619574⟩

Share

Metrics

Record views

415

Files downloads

389