L. Gasienec et al., THE ZOOMING METHOD - A RECURSIVE APPROACH TO TIME-SPACE EFFICIENT STRING-MATCHING, Theoretical computer science, 147(1-2), 1995, pp. 19-30
Citations number
10
Categorie Soggetti
Computer Sciences","Computer Science Theory & Methods
A new approach to time-space efficient string-matching is presented. T
he method is flexible, its implementation depends whether or not the a
lphabet is linearly ordered. The only known linear-time constant-space
algorithm for string-matching over nonordered alphabets is the Galil-
Seiferas algorithm, see Crochemore (1993) and Galil (1983) which are r
ather complicated. The zooming method gives probably the simplest stri
ng-matching algorithm working in constant space and linear time for no
nordered alphabets. The novel feature of our algorithm is the applicat
ion of the searching phase (which is usually simpler than preprocessin
g) in the preprocessing phase. The preprocessing has a recursive struc
ture similar to selection in linear time, see Aho (1974). For ordered
alphabets the preprocessing part is much simpler, its basic component
is a simple and well-known algorithm for finding the maximal suffix, s
ee Duval (1983). Hence we demonstrate a new application of this algori
thm, see also Crochemore (1991). The idea of the zooming method was ap
plied by Crochemore et al. (1995) to two-dimensional patterns.