conference

Computing Covers Under Substring Consistent Equivalence Relations.

Natsumi Kikuchi, Diptarama Hendrian, Ryo Yoshinaka, Ayumi Shinohara

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

開催地: 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.