Finding Frequent Patterns in a String in Sublinear Time

Berenbrink, P.; Ergun, F.; Friedetzky, T.

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. (2005, October). Finding Frequent Patterns in a String in Sublinear Time. Presented at 13th Annual European Symposium on Algorithms : ESA 2005, Ibiza, Spain

• Presentation Conference Type: Conference Paper (published)
• Conference Name: 13th Annual European Symposium on Algorithms : ESA 2005
• Start Date: Oct 3, 2005
• End Date: Oct 6, 2005
• Publication Date: 2005
• Deposit Date: Nov 4, 2008
• Publicly Available Date: Nov 4, 2008
• Print ISSN: 0302-9743
• Peer Reviewed: Peer Reviewed
• Pages: 746-757
• Series Title: Lecture notes in computer science
• Series Number: 3669
• Series ISSN: 0302-9743,1611-3349
• Book Title: Algorithms – ESA 2005
• ISBN: 9783540291183
• DOI: https://doi.org/10.1007/11561071_66
• Public URL: https://durham-repository.worktribe.com/output/1680316
• Publisher URL: http://springerlink.metapress.com/link.asp?id=dw7vk0u166hp2wp9
• Additional Information: October 3–6, 2005.