Efficient detection of quasiperiodicities in strings (Q688155)

A strings \(z\) is quasiperiodic if there is a string \(w\neq z\) such that \(z\) is completely by (possibly overlapping) occurrences of \(w\) in \(z\). In this situation \(w\) is called a quasiperiod of \(z\). If \(z\) is quasiperiodic, then its shortest quasiperiod \(w\) is uniquely determined and is referred to as the quasiperiod of \(z\). (In this case \(w\) itself will not be quasiperiodic; such strings are called by the authors superprimitive. The problem addressed by this paper is to find maximal quasiperiodic substrings (and their quasiperiods) for a given string \(x\). The main result is the construction of an algorithm to find all maximal quasiperiodic substrings of a given string \(x\) in time \(O(n\log^ 2 n)\),where \(n\) is the length of \(x\). The algorithm begins with the construction of a suffix tree for the given string \(x\). It then processes the tree in a bottom-up manner to discover, sort into appropriate lists, and test candidates for quasiperiodicities of \(x\). At the end of the process all maximal quasiperiodic substrings (and their quasiperiods) will have been discovered. A careful analysis of the structure of the suffix tree, of the actions to be performed during the processing, and of the data structures which will need to be maintained enable the authors to establish the \(O(n\log^ 2 n)\) time bound and a linear space bound for the algorithm.