caa a22 4500 445805269 CHVBK 20180317145154.0 cr unu---uuuuu 170323e20111101xx s 000 0 eng 10.1007/s00453-010-9424-y doi (NATIONALLICENCE)springer-10.1007/s00453-010-9424-y Burton Benjamin School of Mathematics and Physics, The University of Queensland, QLD 4072, Brisbane, Australia aut Searching a Bitstream in Linear Time for the Longest Substring of Any Given Density [Elektronische Daten] [Benjamin 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 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. Springer Science+Business Media, LLC, 2010 Algorithms nationallicence String processing nationallicence Substring density nationallicence Randomness testing nationallicence Bioinformatics nationallicence Algorithmica Springer-Verlag 61/3(2011-11-01), 555-579 0178-4617 61:3<555 2011 61 453 https://doi.org/10.1007/s00453-010-9424-y text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00453-010-9424-y text/html Onlinezugriff via DOI NATIONALLICENCE 100 1- Burton Benjamin School of Mathematics and Physics, The University of Queensland, QLD 4072, Brisbane, Australia aut NATIONALLICENCE 773 0- Algorithmica Springer-Verlag 61/3(2011-11-01), 555-579 0178-4617 61:3<555 2011 61 453 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer