The Average Common Substring (ACS) is a popular alignment-free distance measure for phylogeny reconstruction. The ACS can be computed in O(n) space and time, where n=x+y is the input size. The compressed string matching is the study of string matching problems with the following twist: the input data is in a compressed format and the underling task must be performed with little or no decompression. In this paper, we revisit the ACS problem under this paradigm where the input sequences are given in their run-length encoded format. We present an algorithm to compute ACS(X,Y) in O(Nlog N) time using O(N) space, where N is the total length of sequences after run-length encoding.
The computation of ACS is straightforward in @math space and time using the generalized suffix tree of @math and @math , where @math is the input size @cite_12 . In this paper, we study the problem of computing ACS, where the input sequences are @math and @math , where @math (resp., @math ) is the sequence corresponding to the run-length encoding of @math (resp., @math ). Run-length encoding is a simple algorithm used for data compression in which runs of data (occurring of the same character on consecutive positions) are stored as a single charter followed by the count of its consecutive occurrences. The challenge here is to design an algorithm for computing ACS in space and time close to @math instead of @math , where @math . We answer this question positively by presenting the following theorem.
@cite_12
2082173153
In this paper we study the problem of finding maximally sized subsets of binary strings (codes) of equal length that are immune to a given number @math of repetitions, in the sense that no two strings in the code can give rise to the same string after @math repetitions. We propose explicit number theoretic constructions of such subsets. In the case of @math repetition, the proposed construction is asymptotically optimal. For @math , the proposed construction is within a constant factor of the best known upper bound on the cardinality of a set of strings immune to @math repetitions. Inspired by these constructions, we then develop a prefixing method for correcting any prescribed number @math of repetition errors in an arbitrary binary linear block code. The proposed method constructs for each string in the given code a carefully chosen prefix such that the resulting strings are all of the same length and such that despite up to any @math repetitions in the concatenation of the prefix and the codeword, the original codeword can be recovered. In this construction, the prefix length is made to scale logarithmically with the length of strings in the original code. As a result, the guaranteed immunity to repetition errors is achieved while the added redundancy is asymptotically negligible.