2
$\begingroup$

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

$\endgroup$
3
  • 3
    $\begingroup$ 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. $\endgroup$
    – user66277
    May 1 at 20:32
  • $\begingroup$ @user66277 maybe you want to convert your comment into an answer. $\endgroup$ May 2 at 18:34
  • $\begingroup$ Sure, converted to answer. $\endgroup$
    – user66277
    May 3 at 15:55

2 Answers 2

2
$\begingroup$

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

$\endgroup$
1
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.