Additional Problem 15: Subsequence Covers (Preliminary version)

$ \def\SMot{\mathit{Subs}} $

A string $x$ is a subsequence cover (subs-cover, in short) of a string $y$ if every position in $y$ belongs to an occurrence of $x$ in $y$ as a subsequence. The subs-covers differ substantially from standard covers:

two shortest subs-covers of a same string can be distinct.
Every binary word of length at least 4 has a nontrivial subs-cover.
Every ternary word of length at least 9 has a nontrivial subs-cover.

Write a linear time algorithm checking if a given string $x$ of length $m$ is a subs-cover of a string $y$ of length $n\gt m$. Assume alphabet is a subset of $\{0,1,\ldots,n-1\}$.

References

P. Panagiotis, S. Pissis, J. Radoszewwski, W. Rytter, T. Walen, and W. Zuba. Subsequence Covers in Strings, accepted to SPIRE 2022.

125 Problems in Text Algorithms

Example

Additional Problem 15: Subsequence Covers (Preliminary version)

References