Tight bounds on the complexity of the Apostolico-Giancarlo algorithm
Maxime Crochemore, Thierry Lecroq, F- Mont--saint--aignan Cedex · HAL (Le Centre pour la Communication Scientifique Directe) · 1996
. The Apostolico-Giancarlo string-matching algorithm is analyzed precisely. We give a tight upper bound of 3 2 n 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. 1 Introduction The string-matching problem consists in finding all occurrences of a pattern in a text. It is a basic problem that occurs in information retrieval, bibliographic search and molecular biology, for example. It has been extensively studied and numerous techniques and algorithms have been designed to solve this problem (see [5] and [10]). Basically, a string-matching algorithm applies the sliding window mechanism as follows. It first initializes the search by aligning the left ends of the pattern and the text. Then, it checks (or scans) if the pattern occurs in the text at the chosen position and eventually shifts the pattern to the right. Finally, it repeats...