License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CPM.2021.6
URN: urn:nbn:de:0030-drops-139570
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/13957/
Badkobeh, Golnaz ;
Charalampopoulos, Panagiotis ;
Pissis, Solon P.
Internal Shortest Absent Word Queries
Abstract
Given a string T of length n over an alphabet Σ ⊂ {1,2,…,n^{?(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. For any positive integer k ∈ [1,log log_σ n], we present an ?((n/k)⋅ log log_σ n)-size data structure, which can be constructed in ?(nlog_σ n) time, and answers queries in time ?(log log_σ k).
BibTeX - Entry
@InProceedings{badkobeh_et_al:LIPIcs.CPM.2021.6,
author = {Badkobeh, Golnaz and Charalampopoulos, Panagiotis and Pissis, Solon P.},
title = {{Internal Shortest Absent Word Queries}},
booktitle = {32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021)},
pages = {6:1--6:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-186-3},
ISSN = {1868-8969},
year = {2021},
volume = {191},
editor = {Gawrychowski, Pawe{\l} and Starikovskaya, Tatiana},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/13957},
URN = {urn:nbn:de:0030-drops-139570},
doi = {10.4230/LIPIcs.CPM.2021.6},
annote = {Keywords: string algorithms, internal queries, shortest absent word, bit parallelism}
}
|
Keywords: |
|
string algorithms, internal queries, shortest absent word, bit parallelism |
|
Collection: |
|
32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021) |
|
Issue Date: |
|
2021 |
|
Date of publication: |
|
30.06.2021 |
