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).
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.
| Item Type: | Book chapter |
|---|---|
| Full text: | PDF - Accepted Version (197Kb) |
| Status: | Peer-reviewed |
| Publisher Web site: | http://dx.doi.org/10.1007/11561071_66 |
| Publisher statement: | The original publication is available at www.springerlink.com |
| Record Created: | 04 Nov 2008 |
| Last Modified: | 16 Jun 2011 09:23 |
Social bookmarking:       | Export: EndNote, Zotero | BibTex |
| Usage statistics | Look up in GoogleScholar | Find in a UK Library |
![[Feed]](/images/RSSwebsmall.jpg)
![[Tweets]](/images/Twitterwebsmall.png)
