Computing Covers Under Substring Consistent Equivalence Relations.
The 27th International Symposium on String Processing and Information Retrieval (SPIRE2020),
Lecture Notes in Computer Science Vol.12303, pp.131-146
(2020), [peer-reviewed]
Event Date:
October 13-15, 2020
@ online
Abstract / 概要
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 $\approx$ over strings is called a substring consistent equivalence relation (SCER) iff $X \approx Y$ implies (1) $|X|=|Y|$ and (2) $X[i:j] \approx Y[i:j]$ for all $1 \leq i \leq j \leq |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.