Faster algorithms for δ, γ-matching and related problems

P Clifford, R Clifford, CS Iliopoulos

Research output: Contribution to journalArticle (Academic Journal)peer-review

34 Citations (Scopus)

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 contributionFaster algorithms for δ, γ-matching and related problems
Original languageEnglish
Pages (from-to)68 - 78
Number of pages11
JournalLecture Notes in Computer Science
Volume3537
DOIs
Publication statusPublished - 2005

Bibliographical note

ISBN: 3540262016
Publisher: 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

Fingerprint

Dive into the research topics of 'Faster algorithms for δ, γ-matching and related problems'. Together they form a unique fingerprint.

Cite this