# 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.