Tight bounds on the complexity of the Apostolico-Giancarlo algorithm
Résumé
The Apostolico-Giancarlo string-matching algorithm is analyzed precisely. We give a tight upper bound of 3n/2 text characters comparisons when searching for a pattern in a text of length n. We exhibit a family of patterns and texts reaching this bound. We also provide a slightly improved version of the algorithm.
Origine : Fichiers produits par l'(les) auteur(s)