Scattered Factor-Universality of Words

A word [Formula: see text] is a scattered factor of a word w if u can be obtained from w by deleting some of its letters: there exist the (potentially empty) words [Formula: see text] such that [Formula: see text]. The set of all scattered factors up to length k of a word is called its full k-spectrum. Firstly, we show an algorithm deciding whether the k-spectra for given k of two words are equal or not, running in optimal time. Secondly, we consider a notion of scattered-factors universality: the word w, with [Formula: see text], is called k-universal if its k-spectrum includes all words of length k over the alphabet [Formula: see text]; we extend this notion to k-circular universality. After a series of preliminary combinatorial results, we present an algorithm computing, for a given [Formula: see text]-universal word w the minimal i such that [Formula: see text] is k-universal for some [Formula: see text]. Several other connected problems are also considered.