论文标题
单词的分散因素
Scattered Factor-Universality of Words
论文作者
论文摘要
如果可以通过删除其一些字母来从$ w $获得$ w $的零散因素$ u = u_1 \ dots u_n $是通过删除其某些字母从$ w $获得的散射因素：存在（可能为空的）单词$ v_0，v_1，v_1，..，v_n $，例如$ w = v_0u_1v_1 v_0u_1v_1 ... u__nv_nv_nv_n $。所有单词的零散因素的集合称为其完整的$ k $ -spectrum。首先，我们展示了一种算法，该算法确定给定的两个单词的$ k $的$ k $ spectra是否在最佳时间内运行。其次，我们考虑一个分散的因素通用性的概念：如果$ \ letters（w）=σ$的$ w $，则称为$ k $ - umiversal，如果其$ k $ -spectrum包含Alphabet $σ$的所有长度$ k $的所有单词;我们将此概念扩展到$ k $ circular的普遍性。经过一系列初步组合结果后，我们提出了一个算法计算，对于给定的$ k'$ - 通用wumper $ w $ the minimal $ i $ $ $ $ $ $ $ w^i $是$ k $ - $ k $ - umiversal，对于一些$ k> k'$。其他几个连接的问题〜也考虑了〜。
A word $u=u_1\dots u_n$ 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 $v_0,v_1,..,v_n$ such that $w = v_0u_1v_1...u_nv_n$. 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 $\letters(w)=Σ$, is called $k$-universal if its $k$-spectrum includes all words of length $k$ over the alphabet $Σ$; we extend this notion to $k$-circular universality. After a series of preliminary combinatorial results, we present an algorithm computing, for a given $k'$-universal word $w$ the minimal $i$ such that $w^i$ is $k$-universal for some $k>k'$. Several other connected problems~are~also~considered.
