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

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$$?

• This would be called the word problem in a (free) monoid. E.g. see the books by Lothaire (www-igm.univ-mlv.fr/~berstel/Lothaire). For $k = 1$ the problem is in polynomial-time using dynamic programming. For 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 $k$ wasn't minimal. By checking all $k$ then, the problem is still in polynomial time. May 1 at 20:32
• @user66277 maybe you want to convert your comment into an answer. May 2 at 18:34
• Sure, converted to answer. May 3 at 15:55

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\}$$.
(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.