TIGHT BOUNDS ON THE COMPLEXITY OF THE APOSTOLICO-GIANCARLO ALGORITHM

Authors
CROCHEMORE M LECROQ T
Citation
M. Crochemore et T. Lecroq, TIGHT BOUNDS ON THE COMPLEXITY OF THE APOSTOLICO-GIANCARLO ALGORITHM, Information processing letters, 63(4), 1997, pp. 195-203
Citations number
10
Categorie Soggetti
Information Science & Library Science","Computer Science Information Systems
Journal title
Information processing letters → ACNP
ISSN journal
00200190
Volume
63
Issue
4
Year of publication
1997
Pages
195 - 203
Database
ISI
SICI code
0020-0190(1997)63:4<195:TBOTCO>2.0.ZU;2-W
Abstract
The Apostolico-Giancarlo string-matching algorithm is analyzed precise ly. We give a tight upper bound of 3/2n text character comparisons whe n searching for a pattern in a text of length n. We exhibit a family o f patterns and texts reaching this bound. We also provide a slightly i mproved version of the algorithm. (C) 1997 Elsevier Science B.V.