Berenbrink, P. and Ergun, F. and Friedetzky, T. (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. Berlin: Springer, pp. 746-757. Lecture notes in computer science. (3669).
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.
|Item Type:||Book chapter|
|Full text:||PDF (Copyright agreement prohibits open access to the full-text) - Accepted Version |
Publisher-imposed embargo (197Kb)
|Publisher Web site:||http://dx.doi.org/10.1007/11561071_66|
|Record Created:||04 Nov 2008|
|Last Modified:||09 Oct 2014 13:05|
|Social bookmarking:||Export: EndNote, Zotero | BibTex|
|Usage statistics||Look up in GoogleScholar | Find in a UK Library|