A unifying look at the Apostolico-Giancarlo string-matching algorithm

Abstract : String matching is the problem of finding all the occurrences of a pattern in a text. We present a new method to compute the combinatorial shift function ("matching shift") of the well-known Boyer-Moore string matching algorithm. This method implies the computation of the length of the longest suffixes of the pattern ending at each position in this pattern. These values constituted an extra-preprocessing for a variant of the Boyer-Moore algorithm designed by Apostolico and Giancarlo. We give here a new presentation of this algorithm that avoids extra preprocessing together with a tight bound of 1.5n character comparisons (where n is the length of the text).
Document type :
Journal articles
Complete list of metadatas

Cited literature [21 references]  Display  Hide  Download

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

File

jda1.pdf
Files produced by the author(s)

Identifiers

Citation

Maxime Crochemore, Christophe Hancart, Thierry Lecroq. A unifying look at the Apostolico-Giancarlo string-matching algorithm. Journal of Discrete Algorithms, Elsevier, 2003, 1 (1), pp.37-52. ⟨10.1016/S1570-8667(03)00005-4⟩. ⟨hal-00619563⟩

Share

Metrics

Record views

317

Files downloads

505