Cookies

We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.


Durham Research Online
You are in:

Finding frequent patterns in a string in sublinear time.

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: del.icio.usConnoteaBibSonomyCiteULikeFacebookTwitterExport: EndNote, Zotero | BibTex
Usage statisticsLook up in GoogleScholar | Find in a UK Library