An algorithmic toolbox for periodic partial words

作者：Manea Florin^*; Mercas Robert; Tiseanu Catalin

来源：Discrete Applied Mathematics, 2014, 179: 174-192.

DOI：10.1016/j.dam.2014.07.017

• Combinatorics on words
• Periodicity
• Partial words
• Algorithms

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 n are determined in O(n log n) time. Moreover, we define algorithms and data structures that help us answer in constant time queries regarding the periodicity of a word%26apos;s factors. For these we need an O(n(2)) preprocessing time and an 0(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 w with holes, where the distance between two consecutive holes must be greater than a given number, can be done in optimal time O(vertical bar w vertical bar). 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.

• 出版日期2014-12-31