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

DOI10.1007/S00453-010-9424-YzbMATH Open1225.68274arXiv0910.3503OpenAlexW2114709104MaRDI QIDQ644795FDOQ644795

Authors: Benjamin A. Burton 

Publication date: 7 November 2011

Published in: Algorithmica (Search for Journal in Brave)

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.

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

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

zbMATH Keywords

bioinformaticslinear time algorithmstring processingrandomness testingsubstring density

Mathematics Subject Classification ID

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

Cites Work

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

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)