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

Benjamin A. Burton

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 al…