Faster algorithms for δ, γ-matching and related problems

P Clifford; R Clifford; CS Iliopoulos

doi:10.1007/11496656_7

Faster algorithms for δ, γ-matching and related problems

P Clifford, R Clifford, CS Iliopoulos

Research output: Contribution to journal › Article (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 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	https://doi.org/10.1007/11496656_7
Publication status	Published - 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

Access to Document

10.1007/11496656_7

http://www.springerlink.com/content/pvadxkuxkk9crqj9/?p=f616ead61ff1451b9142cde55f7cad57&pi=0

Handle.net

Persistent link

Cite this

@article{261c87b9e0724090914df6b77ae28722,

title = "Faster algorithms for δ, γ-matching and related problems",

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.",

author = "P Clifford and R Clifford and CS Iliopoulos",

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",

year = "2005",

doi = "10.1007/11496656_7",

language = "English",

volume = "3537",

pages = "68 -- 78",

journal = "Lecture Notes in Computer Science",

publisher = "Springer Berlin Heidelberg",

}

TY - JOUR

T1 - Faster algorithms for δ, γ-matching and related problems

AU - Clifford, P

AU - Clifford, R

AU - Iliopoulos, CS

N1 - 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

PY - 2005

Y1 - 2005

N2 - 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.

AB - 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.

U2 - 10.1007/11496656_7

DO - 10.1007/11496656_7

M3 - Article (Academic Journal)

VL - 3537

SP - 68

EP - 78

JO - Lecture Notes in Computer Science

JF - Lecture Notes in Computer Science

ER -

Faster algorithms for δ, γ-matching and related problems

Abstract

Bibliographical note

Access to Document

Handle.net

Fingerprint

Cite this