Periods in partial words: An algorithm

Partial words   are finite sequences over a finite alphabet that may contain some holes. A variant of the celebrated Fine–Wilf theorem shows the existence of a bound L=L(h,p,q)L=L(h,p,q) such that if a partial word of length at least L with h holes has periods p and q  , then it also has period gcd(p,q)gcd(p,q). In this paper, we associate a graph with each p- and q-periodic word, and study two types of vertex connectivity on such a graph: modified degree connectivity and r  -set connectivity where r=qmodp. As a result, we give an algorithm for computing L(h,p,q)L(h,p,q) in the general case and show how to use it to derive the closed formulas.