Abstract. In the second part of the paper, an extended problem of the reconstruction of a word from a set of its subwords is considered. It is assumed that the set is generated by unit shifts of a fixed window along an unknown word. In the new variant, feasible solutions must satisfy additional constraints. The case where these constraints are defined by forbidden words is considered. A solution is proposed based on the search for Euler paths or Euler cycles in a de Bruijn multidigraph with additional operation of edge reduction. After that, symbolic multiplication of adjacency matrices is applied in the same way as in the first part of the paper.

Keywords: reconstruction of words, forbidden word, Euler path, de Bruijn multidigraph, combinatorics of words.