2023-06-21
Linear-time computation of cyclic roots and cyclic covers of a string
Publication
Publication
Cyclic versions of covers and roots of a string are considered in this paper. A prefix V of a string S is a cyclic root of S if S is a concatenation of cyclic rotations of V . A prefix V of S is a cyclic cover of S if the occurrences of the cyclic rotations of V cover all positions of S. We present O(n)-time algorithms computing all cyclic roots (using number-theoretic tools) and all cyclic covers (using tools related to seeds) of a length-n string over an integer alphabet. Our results improve upon O(n log log n) and O(n log n) time complexities of recent algorithms of Grossi et al. (WALCOM 2023) for the respective problems and provide novel approaches to the problems. As a by-product, we obtain an optimal data structure for Internal Circular Pattern Matching queries that generalize Internal Pattern Matching and Cyclic Equivalence queries of Kociumaka et al. (SODA 2015).
| Additional Metadata | |
|---|---|
| , , , | |
| doi.org/10.4230/LIPIcs.CPM.2023.15 | |
| Leibniz International Proceedings in Informatics, LIPIcs | |
| Networks | |
| 34th Annual Symposium on Combinatorial Pattern Matching, CPM 2023 | |
| Organisation | Centrum Wiskunde & Informatica, Amsterdam (CWI), The Netherlands |
|
Iliopoulos, C., Kociumaka, T., Radoszewski, J., Rytter, W., Waleń, T., & Zuba, W. (2023). Linear-time computation of cyclic roots and cyclic covers of a string. In Proceedings of the 34th Annual Symposium on Combinatorial Pattern Matching, CPM 2023 (pp. 15:1–15:15). doi:10.4230/LIPIcs.CPM.2023.15 |
|
