Abstract
We present new faster algorithms for the
problems of δ and (δ, γ)-matching on numeric strings. In both cases the running time of the proposed algorithms is shown
to be
O(δ n log m), where m is the pattern length, n is
the text length and δ a given integer. Our approach makes use
of Fourier transform methods and the running times are independent of the
alphabet size. O(n\sqrt(m log m) algorithms for the γ -matching and total-difference problems are also given.
In all the above cases, we improve existing running time bounds in
the literature.
Translated title of the contribution | Faster algorithms for δ, γ-matching and related problems |
---|---|
Original language | English |
Pages (from-to) | 68 - 78 |
Number of pages | 11 |
Journal | Lecture Notes in Computer Science |
Volume | 3537 |
DOIs | |
Publication status | Published - 2005 |
Bibliographical note
ISBN: 3540262016Publisher: Springer
Name and Venue of Conference: 16th Annual Symposium on Combinatorial Pattern Matching (CPM 2005), Jeju Island, Korea, June 19-22
Other: http://www.cs.bris.ac.uk/Publications/pub_info.jsp?id=2000455