Reconstruction of a word from a multiset of its factors
Let D-k(w) be the multiset containing all factors of w of length k including repetitions. One of the main results is that if D-k(w)= D-k(upsilon) for all k <=[vertical bar w vertical bar/2] +1 then w=upsilon. The bond [vertical bar w vertical bar/2] +1 is optimal; however we also show that if D-k(w)=Dk(upsilon) fork <= [vertical bar w vertical bar/2], then w and upsilon are structurally similar. (c) 2008 Elsevier B.V. All rights reserved.
combinatorics on words repeated factors