Seeking references on writing a long string $\ell$ as concatenation of shorter strings $s_1, s_2, s_3, ...$

Question

Given: a (long binary) string $\ell$, and a set of (short) strings, $s_1, s_2, ...$ . Can $\ell$ be written as concatenation of the short strings? I am looking for references on: the name of the problem, text or papers, algorithms or calculators.

Similar problems or other wordings:

Let $S=\{s_1,s_2, ...\}$. Is there $n$ such that $\ell$ belongs to $S^n$? Are there $m,k$ such that $\ell^k$ belongs to $S^m$?

Let $L=\{\ell_1,\ell_2, ...\}$. Find smallest $k$ such that an element of $L^k$ is in an $S^m$?

Answer 1

This is part of coding theory if you view $\ell$ as a message and $s_i$ as its components. As such, it is studied in bioinformatics as well, where the underlying alphabet could be $\{A,C,G,T\}$.

Answer 2

(Earlier as comment). This would be called the word problem in a (free) monoid. E.g. see the books by Lothaire (https://www-igm.univ-mlv.fr/~berstel/Lothaire). For k=1 the problem is in polynomial-time using dynamic programming. For the power of a word, $\ell^k$ you can show that it is sufficient to check $k \leq \sum |s_i|$. (If bigger $k$ were necessary, then there would be two different occurrences of $\ell\ell$ in which the boundary between the two $\ell$ is matched with the same $s_i$ in the same position, which means that $k$ wasn't minimal. By checking all $k$ then, the problem is still in polynomial time.