 |
HAL UPEC - UPEM Portal |  |
 |
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).
Cited literature [21 references]
https://hal-upec-upem.archives-ouvertes.fr/hal-00619563
Contributor : Maxime Crochemore Connect in order to contact the contributor
Submitted on : Tuesday, March 19, 2013 - 5:09:31 PM
Last modification on : Tuesday, October 19, 2021 - 4:14:59 PM
Long-term archiving on: : Thursday, June 20, 2013 - 4:20:50 PM
Contributor : Maxime Crochemore Connect in order to contact the contributor
Submitted on : Tuesday, March 19, 2013 - 5:09:31 PM
Last modification on : Tuesday, October 19, 2021 - 4:14:59 PM
Long-term archiving on: : Thursday, June 20, 2013 - 4:20:50 PM
File
jda1.pdf
Files produced by the author(s)