Fast optimal algorithms for computing all the repeats in a string
MetadataShow full item record
Given a string x = x[1..n] on an alphabet of size a, and a threshold pmin = 1, we first describe a new algorithm PSY1 that, based on suffix array construction, computes all the complete nonextendible repeats in x of length p = pmin. PSY1 executes in Θ(n) time independent of alphabet size and is an order of magnitude faster than the two other algorithms previously proposed for this problem. Second, we describe a new fast algorithm PSY2 for computing all complete supernonextendible repeats in x that also executes in Θ(n) time independent of alphabet size, thus asymptotically faster than methods previously proposed. Both algorithms require 9n bytes of storage, including preprocessing (with a minor caveat for PSY1). We conclude with a brief discussion of applications to bioinformatics and data compression.
Showing items related by title, author, creator and subject.
Adaptive antenna array beamforming using a concatenation of recursive least square and least mean square algorithmsSrar, Jalal Abdulsayed (2011)In recent years, adaptive or smart antennas have become a key component for various wireless applications, such as radar, sonar and cellular mobile communications including worldwide interoperability for microwave ...
Kulanoot, Araya (2000)The Knapsack Problems are among the simplest integer programs which are NP-hard. Problems in this class are typically concerned with selecting from a set of given items, each with a specified weight and value, a subset ...
Huo, Jia Q. (1999)Adaptive filters have found applications in many signal processing problems. In some situations, linear constraints are imposed on the filter weights such that the filter is forced to exhibit a certain desired response. ...