Computing Covers under Substring Consistent Equivalence Relations

02/17/2020
by   Natsumi Kikuchi, et al.
0

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

Please sign up or login with your details

Forgot password? Click here to reset