Fragment assembly through minimal forbidden words

We give a linear-time algorithm to reconstruct a nite word w over a nite alphabet A of constant size starting from a nite set of fac- tors of w verifying a suitable hypothesis. We use combinatorics techniques based on the minimal forbidden words, which have been introduced in pre- vious papers. This improves a previous algorithm which worked under the assumption of stronger hypothesis.