P. Berenbrink
Finding frequent patterns in a string in sublinear time
Berenbrink, P.; Ergun, F.; Friedetzky, T.; Brodal, G.S.; Leonardi, S.
Authors
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
Accepted Conference Proceeding
(201 Kb)
PDF
Copyright Statement
The final publication is available at Springer via http://dx.doi.org/10.1007/11561071_66