Computing Covers under Substring Consistent Equivalence Relations
share
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 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.
READ FULL TEXT