2022-06-27
Linear-time computation of shortest covers of all rotations of a string
Publication
Publication
We show that lengths of shortest covers of all rotations of a length-n string over an integer alphabet can be computed in O(n) time in the word-RAM model, thus improving an O(nlog n)-time algorithm from Crochemore et al. (Theor. Comput. Sci., 2021). Similarly as Crochemore et al., we use a relation of covers of rotations of a string S to seeds and squares in S3. The crucial parameter of a string S is the number ξ(S) of primitive covers of all rotations of S. We show first that the time complexity of the algorithm from Crochemore et al. can be slightly improved which results in time complexity Θ(ξ(S)). However, we also show that in the worst case ξ(S) is Ω(|S|log |S|). This is the main difficulty in obtaining a linear time algorithm. We overcome it and obtain yet another application of runs in strings.
| Additional Metadata | |
|---|---|
| , , , , | |
| doi.org/10.4230/LIPIcs.CPM.2022.22 | |
| Leibniz International Proceedings in Informatics (LIPIcs) | |
| Networks | |
| Annual Symposium on Combinatorial Pattern Matching | |
| Organisation | Centrum Wiskunde & Informatica, Amsterdam (CWI), The Netherlands |
|
Crochemore, M., Iliopoulos, C., Radoszewski, J., Rytter, W., Straszyński, J., Waleń, T., & Zuba, W. (2022). Linear-time computation of shortest covers of all rotations of a string. In 33rd Annual Symposium on Combinatorial Pattern Matching (pp. 22:1–22:15). doi:10.4230/LIPIcs.CPM.2022.22 |
|
