Name
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 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 \le i \le j \le |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. |
Year | DOI | Venue |
|---|---|---|
2020 | 10.1007/978-3-030-59212-7_10 | SPIRE |
DocType | Citations | PageRank |
Conference | 0 | 0.34 |
References | Authors | |
0 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Kikuchi Natsumi | 1 | 0 | 0.34 |
| Hendrian Diptarama | 2 | 0 | 1.01 |
| Ryo Yoshinaka | 3 | 172 | 26.19 |
| Ayumi Shinohara | 4 | 936 | 88.28 |