Skip to main content

Research Repository

Advanced Search

Finding frequent patterns in a string in sublinear time

Berenbrink, P.; Ergun, F.; Friedetzky, T.; Brodal, G.S.; Leonardi, S.

Finding frequent patterns in a string in sublinear time Thumbnail


Authors

P. Berenbrink

F. Ergun

T. Friedetzky

G.S. Brodal

S. Leonardi



Abstract

We consider the problem of testing whether (a large part of) a given string X of length n over some finite alphabet is covered by multiple occurrences of some (unspecified) pattern Y of arbitrary length in the combinatorial property testing model. Our algorithms randomly query a sublinear number of positions of X, and run in sublinear time in n. We first focus on finding patterns of a given length, and then discuss finding patterns of unspecified length.

Citation

Berenbrink, P., Ergun, F., Friedetzky, T., Brodal, G., & Leonardi, S. (2005). Finding frequent patterns in a string in sublinear time. In Algorithms - ESA 2005 : 13th Annual European Symposium, 3-6 October 2005, Palma de Mallorca, Spain ; proceedings (746-757). https://doi.org/10.1007/11561071_66

Conference Name 13th Annual European Symposium on Algorithms : ESA 2005
Conference Location Ibiza, Spain
Start Date Oct 3, 2005
End Date Oct 6, 2005
Publication Date 2005-10
Deposit Date Nov 4, 2008
Publicly Available Date Nov 4, 2008
Pages 746-757
Series Title Lecture notes in computer science
Series Number 3669
Series ISSN 0302-9743,1611-3349
Book Title Algorithms - ESA 2005 : 13th Annual European Symposium, 3-6 October 2005, Palma de Mallorca, Spain ; proceedings.
ISBN 9783540291183
DOI https://doi.org/10.1007/11561071_66
Publisher URL http://springerlink.metapress.com/link.asp?id=dw7vk0u166hp2wp9
Additional Information October 3–6, 2005.

Files



Downloadable Citations