CLR cover

Example

\( \def\sa#1{\tt{#1}} \def\dd{\dot{}\dot{}} \)

The word $x=\sa{010}$ is a (shortest) s-cover of $y=\sa{0110110}$ as well as of $y=\sa{000011000}$. However, $x=\sa{010010}$ is not.

Problem 138: Subsequence covers

\( \def\SMot{\mathit{Subs}} \)

A word $x$ is a subsequence cover (s-cover, in short) of a word $y$ if each position on $y$ belongs to an occurrence of $x$ as a subsequence of $y$.

Let $y$ be a word in $\{0,1,\ldots,n-1\}^n$. Design a linear-time algorithm that checks if a given word $x$ of length $m\lt n$ is an s-cover of $y$.

References

P. Charalampopoulos, S. P. Pissis, J. Radoszewski, W. Rytter, T. Walen, and W. Zuba, Subsequence covers of words, In D. Arroyuelo and B. Poblete, editors, Proceeding of the 29th International Symposium String Processing and Information Retrieval SPIRE 2022 Concepción, Chile, 2022, volume 13617 of Lecture Notes in Computer Science, pages 3-15. Springer.