%0 Journal Article
%T Searching a bitstream in linear time for the longest substring of any given density
%A Benjamin A. Burton
%J Computer Science
%D 2009
%I arXiv
%R 10.1007/s00453-010-9424-y
%X 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.
%U http://arxiv.org/abs/0910.3503v2