2020/02/17 by Natsumi Kikuchi, Kikuchi, Natsumi, Diptarama Hendrian +5 · 2 citations
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.2002.06764
openalex publication_date 2020/02/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Covers are a kind of quasiperiodicity in strings. A string C is a cover of another string T if any position of T is inside some occurrence of C in T. The shortest and longest cover arrays of T have the lengths of the shortest and longest covers of each prefix of T, respectively. The literature has proposed linear-time algorithms computing longest and shortest cover arrays taking border arrays as input. An equivalence relation ≈ over strings is called a substring consistent equivalence relation (SCER) iff X ≈ Y implies (1) |X| = |Y| and (2) X[i:j] ≈ Y[i:j] for all 1 ≤ i ≤ j ≤ |X|. In this paper, we generalize the notion of covers for SCERs and prove that existing algorithms to compute the shortest cover array and the longest cover array of a string T under the identity relation will work for any SCERs taking the accordingly generalized border arrays.