A subsequence of a word $w$ is a word $u$ such that $u = w[i_1] w[i_2] , \dots w[i_{|u|}]$, for some set of indices $1 \leq i_1 < i_2 < \dots < i_k \leq |w|$. A word $w$ is $k$-subsequence universal over an alphabet $\Sigma$ if every word in $\Sigma^k$ appears in $w$ as a subsequence. In this paper, we provide new algorithms for $k$-subsequence universal words of fixed length $n$ over the alphabet $\Sigma = \{1,2,\dots, \sigma\}$. Letting $\mathcal{U}(n,k,\sigma)$ denote the set of $n$-length $k$-subsequence universal words over $\Sigma$, we provide: * an $O(n k \sigma)$ time algorithm for counting the size of $\mathcal{U}(n,k,\sigma)$; * an $O(n k \sigma)$ time algorithm for ranking words in the set $\mathcal{U}(n,k,\sigma)$; * an $O(n k \sigma)$ time algorithm for unranking words from the set $\mathcal{U}(n,k,\sigma)$; * an algorithm for enumerating the set $\mathcal{U}(n,k,\sigma)$ with $O(n \sigma)$ delay after $O(n k \sigma)$ preprocessing.
翻译：一个单词w的子序列是一个单词u，使得 $u = w [i_1] w [i_2]，\dots w [i_k] $，其中 $1 \leq i_1 <i_2 <\dots <i_k \leq |w|$。 如果在单词$w$中作为子序列出现了$\Sigma^k$中的每个词，则单词$w$是关于字母表$\Sigma$的k-子序列通用的。 在本文中，我们提供了关于固定长度$n$但字母表$\Sigma = \{1,2，\dots，\sigma\}$的$k$-子序列通用词的新算法。 让$\mathcal{U}(n,k,\sigma)$表示字母表$\Sigma$上的$n$-长度$k$-子序列通用词的集合，我们提供以下内容：*计算$\mathcal{U}(n,k,\sigma)$大小的$O(nk\sigma)$时间算法; *在集合$\mathcal{U}(n,k,\sigma)$中排名单词的$O(n k \sigma)$时间算法; *从$\mathcal{U}(n,k,\sigma)$集合中反排名单词的$O(nk\sigma)$时间算法; *在$O(nk\sigma)$预处理后，枚举集合$\mathcal{U}(n,k,\sigma)$的算法与$O(n\sigma)$延迟。
相关内容
微信扫码咨询专知VIP会员