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

Maxime Crochemore (1) , Christophe Hancart (2) , Thierry Lecroq (2)

1 LIGM - Laboratoire d'Informatique Gaspard-Monge
2 LIFAR - Laboratoire d'informatique fondamentale et appliquée de Rouen

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).

Domaines: Algorithme et structure de données [cs.DS]

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