Periodicity Algorithms and a Conjecture on Overlaps in Partial Words *

Abstract We propose an algorithm that given as input a full word w of length n, and positive integers p and d, outputs, if any exists, a maximal pperiodic partial word contained in w with the property that no two holes are within distance d (so-called d-valid). Our algorithm runs in O(nd) time and is used for the study of repetition-freeness of partial words. Furthermore, we construct an infinite word over a five-letter alphabet that is overlap-free even after holes are inserted in arbitrary 2-valid positions, answering affirmatively a conjecture from BlanchetSadri, Mercaş, and Scott