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