2026-01-02
Finding the cyclic covers of a string
Publication
Publication
Information Processing Letters , Volume 191 p. 106594:1- 106594:7
We introduce the concept of cyclic covers, which generalizes the classical notion of covers in strings. Given any string $\mathit{X}$, a factor $\mathit{W}$ of $\mathit{X}$ is called a cyclic cover if each position of $\mathit{X}$ belongs to an occurrence of a cyclic shift of $\mathit{W}$ in $\mathit{X}$. Two cyclic covers are distinct if one is not a cyclic shift of the other. The cyclic covers problem asks for all distinct cyclic covers of an input string $\mathit{X}$. We present an algorithm that solves the cyclic covers problem in $\mathscr O(n \log n)$ time, where ${n}$ is the length of $\mathit{X}$. It is based on finding a well-structured set of standard occurrences of a constant number of factors of a cyclic cover candidate $\mathit{W}$, computing the regions of $\mathit{X}$ covered by cyclic shifts of $\mathit{W}$, extending those factors, and taking the union of the results.
| Additional Metadata | |
|---|---|
| , , , , | |
| doi.org/10.1016/j.ipl.2025.106594 | |
| Information Processing Letters | |
| Organisation | Centrum Wiskunde & Informatica, Amsterdam (CWI), The Netherlands |
|
Grossi, R., Iliopoulos, C., Jansson, J., Lim, Z., Sung, W.-K., & Zuba, W. (2026). Finding the cyclic covers of a string. Information Processing Letters, 191, 106594:1–106594:7. doi:10.1016/j.ipl.2025.106594 |
|
