2023/04/10 by Adamson, Duncan
#Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.2304.04583
A subsequence of a word w is a word u such that u = w[i1] w[i2] , … w[i|u|], for some set of indices 1 ≤ i1 < i2 < … < ik ≤ |w|. A word w is k-subsequence universal over an alphabet Σ if every word in Σ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 Σ= \1,2,…, σ\. Letting U(n,k,σ) denote the set of n-length k-subsequence universal words over Σ, we provide: * an O(n k σ) time algorithm for counting the size of U(n,k,σ); * an O(n k σ) time algorithm for ranking words in the set U(n,k,σ); * an O(n k σ) time algorithm for unranking words from the set U(n,k,σ); * an algorithm for enumerating the set U(n,k,σ) with O(n σ) delay after O(n k σ) preprocessing.