Tight bounds on the complexity of the Apostolico-Giancarlo algorithm

Maxime Crochemore (1) , Thierry Lecroq (2)

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

The Apostolico-Giancarlo string-matching algorithm is analyzed precisely. We give a tight upper bound of 3n/2 text character 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.

Mots clés: string matching; analysis of algorithms; computational complexity

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

Maxime Crochemore, Thierry Lecroq. Tight bounds on the complexity of the Apostolico-Giancarlo algorithm. Information Processing Letters, 1997, 63 (4), pp.195-203. ⟨10.1016/S0020-0190(97)00107-5⟩. ⟨hal-00619574⟩