An algorithmic toolbox for periodic partial words

This work presents efficient solutions to several basic algorithmic problems regarding periodicity of partial words. In the first part of the paper, we show that all periods of a partial word of length nn are determined in O(nlogn)O(nlogn) time. Moreover, we define algorithms and data structures that help us answer in constant time queries regarding the periodicity of a word’s factors. For these we need an O(n2)O(n2) preprocessing time and an O(n)O(n) updating time, whenever the words are extended by adding a letter. In the second part of the paper, we show that identifying a way to construct a periodic partial word by substituting the letters on some positions of a full word ww with holes, where the distance between two consecutive holes must be greater than a given number, can be done in optimal time O(|w|)O(|w|). We also show that identifying a substitution which replaces the minimum number of positions by holes can be done as fast as in the previous case.