2023-03-13
Finding the cyclic covers of a string
Publication
Publication
We introduce the concept of cyclic covers, which generalizes the classical notion of covers in strings. Given any nonempty string X of length n, a factor W of X is called a cyclic cover if every position of X belongs to an occurrence of a cyclic shift of W. Two cyclic covers are distinct if one is not a cyclic shift of the other. The cyclic cover problem requires finding all distinct cyclic covers of X. We present an algorithm that solves the cyclic cover problem in time. This is based on finding a well-structured set of standard occurrences of a constant number of factors of a cyclic cover candidate W, computing the regions of X covered by cyclic shifts of W, extending those factors, and taking the union of the results.
| Additional Metadata | |
|---|---|
| , , , , | |
| doi.org/10.1007/978-3-031-27051-2_13 | |
| Lecture Notes in Computer Science/Lecture Notes in Artificial Intelligence | |
| 17th International Conference and Workshops on Algorithms and Computation, WALCOM 2023 | |
| Organisation | Centrum Wiskunde & Informatica, Amsterdam (CWI), The Netherlands |
|
Grossi, R., Iliopoulos, C., Jansson, J., Lim, Z., Sung, W.-K., & Zuba, W. (2023). Finding the cyclic covers of a string. In International Conference and Workshops on Algorithms and Computation, WALCOM 2023 (pp. 139–150). doi:10.1007/978-3-031-27051-2_13 |
|
