Searching a bitstream in linear time for the longest substring of any given density

Burton, Benjamin A. (2011) Searching a bitstream in linear time for the longest substring of any given density. Algorithmica, 61 3: 555-579. doi:10.1007/s00453-010-9424-y

Attached Files (Some files may be inaccessible until you login with your UQ eSpace credentials)
Name Description MIMEType Size Downloads

Author Burton, Benjamin A.
Title Searching a bitstream in linear time for the longest substring of any given density
Journal name Algorithmica   Check publisher's open access policy
ISSN 0178-4617
1432-0541
Publication date 2011-11
Sub-type Article (original research)
DOI 10.1007/s00453-010-9424-y
Open Access Status
Volume 61
Issue 3
Start page 555
End page 579
Total pages 25
Place of publication Springer New York
Publisher New York, NY, United States
Collection year 2012
Language eng
Abstract Given an arbitrary bitstream, we consider the problem of finding the longest substring whose ratio of ones to zeroes equals a given value. The central result of this paper is an algorithm that solves this problem in linear time. The method involves (i) reformulating the problem as a constrained walk through a sparse matrix, and then (ii) developing a data structure for this sparse matrix that allows us to perform each step of the walk in amortised constant time. We also give a linear time algorithm to find the longest substring whose ratio of ones to zeroes is bounded below by a given value. Both problems have practical relevance to cryptography and bioinformatics.
Keyword Algorithms
String processing
Substring density
Randomness testing
Bioinformatics
Q-Index Code C1
Q-Index Status Confirmed Code
Institutional Status UQ

Document type: Journal Article
Sub-type: Article (original research)
Collections: School of Mathematics and Physics
Official 2012 Collection
 
Versions
Version Filter Type
Citation counts: TR Web of Science Citation Count  Cited 2 times in Thomson Reuters Web of Science Article | Citations
Scopus Citation Count Cited 1 times in Scopus Article | Citations
Google Scholar Search Google Scholar
Created: Sun, 04 Sep 2011, 01:15:06 EST by System User on behalf of School of Mathematics & Physics