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

DOI10.1007/S00453-010-9424-YMaRDI QIDQ644795zbMATHOpenAlexFDO

Authors Benjamin A. Burton

Publication date 7 November 2011

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0910.3503

zbMATH Keywords

bioinformaticslinear time algorithmstring processingrandomness testingsubstring density

Mathematics Subject Classification ID

Cryptography (94A60) Algorithms on strings (68W32)

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.

Recommendations

• Testing Stream Ciphers by Finding the Longest Substring of a Given Density
• Locating regions in a sequence under density constraints
• An optimal algorithm for the maximum-density segment problem
• Fast algorithms for the density finding problem
• scientific article; zbMATH DE number 1945161

Cites work

• scientific article; zbMATH DE number 1929960 (Why is no real title available?)
• Dragon: A Fast Word Based Stream Cipher
• Fast and space-efficient location of heavy or dense segments in run-length encoded sequences (extended abstract)
• Introduction to algorithms
• Linear-time algorithms for computing maximum-density sequence segments with bioinformatics applications
• On a new law of large numbers
• Testing Stream Ciphers by Finding the Longest Substring of a Given Density
• The Erdős-Rényi law in distribution, for coin tossing and sequence matching

Cited in

(2)

• Testing Stream Ciphers by Finding the Longest Substring of a Given Density
• Locating regions in a sequence under density constraints

This page was built for publication: Searching a bitstream in linear time for the longest substring of any given density

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q644795)