# Faster algorithms for &delta, &gamma matching and related problems

P. Clifford, Raphael Clifford, C. S. Iliopoulos, Faster algorithms for &delta, &gamma matching and related problems. *Proceedings of the 16th Annual Symposium on Combinatorial Pattern Matching (CPM)*. ISBN 3-540-26201-6, pp. 68–78. April 2005. No electronic version available.
## Abstract

We present new faster algorithms for the
problems of I' and (I', I?)-matching on numeric strings. In both cases the running time of the proposed algorithms is shown
to be
O(I' n log m), where m is the pattern length, n is
the text length and I' 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 I? -matching and total-difference problems are also given.
In all the above cases, we improve existing running time bounds in
the literature.

Bibtex entry.

## Contact details

## Publication Admin