Abstract. The problem of reconstruction of words given a set of its subwords is considered. It is assumed that the set is generated by unit shifts of a fixed window along the unknown word. For the problem without restrictions on the unknown word, a method of reconstruction is proposed based on the search of Euler paths or Euler cycles in the de Bruijn multidigraph. The search is based on symbolic multiplication of the adjacency matrices with specific operations of multiplication and addition of edge names. The method gives both the number of reconstructions and reconstructed words.

Keywords: reconstruction of words, graph, Euler path, enumeration of paths, reconstruction without forbidden words, de Bruijn graph, symbolic matrix multiplication.