We introduce subsequence covers (s-covers, in short), a new type of covers of a word. A word C is an s-cover of a word S if the occurrences of C in S as subsequences cover all the positions in S. The s-covers seem to be computationally much harder than standard covers of words (cf. Apostolico et al. (1991) [1]), but, on the other hand, much easier than the related shuffle powers (Warmuth and Haussler (1984) [6]). We give a linear-time algorithm for testing if a candidate word C is an s-cover of a word S over a polynomially-bounded integer alphabet. We also give an algorithm for finding a shortest s-cover of a word S, which in the case of a constant-sized alphabet, also runs in linear time. The words without proper s-cover are called s-primitive. We complement our algorithmic results with explicit lower and an upper bound on the length of a longest s-primitive word. Both bounds are exponential in the size of the alphabet. The upper bound presented here improves the bound given in the conference version of this paper [SPIRE 2022].

, , , ,
doi.org/10.1016/j.tcs.2025.115216
Theoretical Computer Science
Centrum Wiskunde & Informatica, Amsterdam (CWI), The Netherlands

Charalampopoulos, P., Pissis, S., Radoszewski, J., Rytter, W., Waleń, T., & Zuba, W. (2025). Subsequence covers of words. Theoretical Computer Science, 1041, 115216:1–115216:14. doi:10.1016/j.tcs.2025.115216