Skip to Main content Skip to Navigation
Journal articles

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 metadata

Cited literature [21 references]  Display  Hide  Download
Contributor : Maxime Crochemore Connect in order to contact the contributor
Submitted on : Tuesday, March 19, 2013 - 5:09:31 PM
Last modification on : Saturday, January 15, 2022 - 3:57:32 AM
Long-term archiving on: : Thursday, June 20, 2013 - 4:20:50 PM


Files produced by the author(s)



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⟩



Record views


Files downloads