Adamson, Duncan 
ORCID: 0000-0003-3343-2435
(2023)
Ranking and Unranking k-Subsequence Universal Words.
In: WORDS.
|
Text
Ranking_and_Unranking_k_Universal_Words-7.pdf - Author Accepted Manuscript Available under License Creative Commons Attribution. Download (333kB) | Preview |
|
|
Text
2304.04583.pdf - Author Accepted Manuscript Download (175kB) | Preview |
Abstract
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(nkσ) time algorithm for counting the size of U(n, k, σ) ;an O(nkσ) time algorithm for ranking words in the set U(n, k, σ) ;an O(nkσ) 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(nkσ) preprocessing.
| Item Type: | Conference or Workshop Item (Unspecified) |
|---|---|
| Uncontrolled Keywords: | Clinical Research |
| Divisions: | Faculty of Science and Engineering > School of Physical Sciences |
| Depositing User: | Symplectic Admin |
| Date Deposited: | 09 Jun 2023 15:42 |
| Last Modified: | 15 Mar 2024 15:15 |
| DOI: | 10.1007/978-3-031-33180-0_4 |
| Related URLs: | |
| URI: | https://livrepository.liverpool.ac.uk/id/eprint/3170915 |
Dimensions
Dimensions
