Internal shortest absent word queries in constant time and linear space
Badkobeh, G. 
ORCID: 0000-0001-5550-7149, Charalampopoulos, P., Kosolobov, D. & Pissis, S. P. (2022).
Internal shortest absent word queries in constant time and linear space.
Theoretical Computer Science, 922,
pp. 271-282.
doi: 10.1016/j.tcs.2022.04.029
Abstract
Given a string T of length n over an alphabet Σ⊂{1,2,…,nO(1)} of size σ, we are to preprocess T so that given a range [i,j], we can return a representation of a shortest string over Σ that is absent in the fragment T[i]⋯T[j] of T. We present an O(n)-space data structure that answers such queries in constant time and can be constructed in O(nlogσn) time.
| Publication Type: | Article |
|---|---|
| Additional Information: | © 2024. This manuscript version is made available under the CC-BY-NC-ND 4.0 license https://creativecommons.org/licenses/by-nc-nd/4.0/ |
| Publisher Keywords: | string algorithms, internal queries, shortest absent word, bit parallelism |
| Subjects: | Q Science > QA Mathematics > QA75 Electronic computers. Computer science |
| Departments: | School of Science & Technology School of Science & Technology > Department of Computer Science |
| SWORD Depositor: |
Preview
Available under License Creative Commons Attribution Non-commercial No Derivatives.
Download (419kB) | Preview
Official URL: http://dx.doi.org/10.1016/j.tcs.2022.04.029
Export
Downloads
Downloads per month over past year
Metadata
Metadata
MetadataAltmetric
CORE (COnnecting REpositories)
Actions (login required)
Actions (login required)
Admin Login