Computer Science – Data Structures and Algorithms
Scientific paper
2009-10-19
Algorithmica 61 (2011), no. 3, 555-579
Computer Science
Data Structures and Algorithms
22 pages, 19 figures; v2: minor edits and enhancements
Scientific paper
10.1007/s00453-010-9424-y
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.
No associations
LandOfFree
Searching a bitstream in linear time for the longest substring of any given density does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Searching a bitstream in linear time for the longest substring of any given density, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Searching a bitstream in linear time for the longest substring of any given density will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-716143