2026-07-25T21:33:25Z
https://drops.dagstuhl.de/oai
oai:drops-oai.dagstuhl.de:13957
2024-03-06T10:52:59Z
ddc:004
open_access
Internal Shortest Absent Word Queries
Badkobeh, Golnaz
Charalampopoulos, Panagiotis
Pissis, Solon P.
string algorithms
internal queries
shortest absent word
bit parallelism
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).
Schloss Dagstuhl β Leibniz-Zentrum fΓΌr Informatik
Golnaz Badkobeh and Panagiotis Charalampopoulos and Solon P. Pissis
2021
Is Part Of LIPIcs, Volume 191, 32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021)
InProceedings
Text
doc-type:ResearchArticle
publishedVersion
application/pdf
doi:10.4230/LIPIcs.CPM.2021.6
urn:nbn:de:0030-drops-139570
https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2021.6
eng
https://creativecommons.org/licenses/by/4.0/legalcode