2015/06/22 by Ali Alatabbi, Alatabbi, Ali, Abir Islam +7
Biochemistry, Genetics and Molecular Biology · Computer Science · #Algorithms and Data Compression #DNA and Biological Computing #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1506.06793
openalex publication_date 2015/06/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A \itbfcover of a string x = x[1..n] is a proper substring u of x such that x can be constructed from possibly overlapping instances of u. A recent paper \citeFIKPPST13 relaxes this definition --- an \itbfenhanced cover u of x is a border of x (that is, a proper prefix that is also a suffix) that covers a \it maximum number of positions in x (not necessarily all) --- and proposes efficient algorithms for the computation of enhanced covers. These algorithms depend on the prior computation of the \itbfborder array β[1..n], where β[i] is the length of the longest border of x[1..i], 1 ≤ i ≤ n. In this paper, we first show how to compute enhanced covers using instead the \itbfprefix table: an array π[1..n] such that π[i] is the length of the longest substring of x beginning at position i that matches a prefix of x. Unlike the border array, the prefix table is robust: its properties hold also for \itbfindeterminate strings --- that is, strings defined on \it subsets of the alphabet Σ rather than individual elements of Σ. Thus, our algorithms, in addition to being faster in practice and more space-efficient than those of \citeFIKPPST13, allow us to easily extend the computation of enhanced covers to indeterminate strings. Both for regular and indeterminate strings, our algorithms execute in expected linear time. Along the way we establish an important theoretical result: that the expected maximum length of any border of any prefix of a regular string x is approximately 1.64 for binary alphabets, less for larger ones.