Internal shortest absent word queries in constant time and linear space

Autor: Golnaz Badkobeh, Panagiotis Charalampopoulos, Dmitry Kosolobov, Solon P. Pissis

Publikováno v: CPM 2021-32nd Annual Symposium on Combinatorial Pattern Matching
CPM 2021-32nd Annual Symposium on Combinatorial Pattern Matching, Jul 2021, Wroclaw, Poland. pp.1-13
Badkobeh, G, Charalampopoulos, P, Kosolobov, D & Pissis, S P 2022, ' Internal shortest absent word queries in constant time and linear space ', Theoretical Computer Science, vol. 922, pp. 271-282 . https://doi.org/10.1016/j.tcs.2022.04.029
32nd Annual Symposium on Combinatorial Pattern Matching (CPM)
32nd Annual Symposium on Combinatorial Pattern Matching (CPM), 2021, Wroclaw, Poland
Theoretical Computer Science
Theoretical Computer Science, 922, 271-282. Elsevier
NARCIS
arXiv.org e-Print Archive
Hal-Diderot
Mémoires en Sciences de l'Information et de la Communication
Institutional repository of Ural Federal University named after the first President of Russia B.N.Yeltsin
Vrije Universiteit Amsterdam (VU Amsterdam)-Institutional Repository
INRIA a CCSD electronic archive server
Datacite
ORCID
Theoretical Computer Science, 922, 271-282

Comment: 13 pages, 1 figure, 4 tables
Given a string $T$ of length $n$ over an alphabet $\Sigma\subset \{1,2,\ldots,n^{O(1)}\}$ of size $\sigma$, we are to preprocess $T$ so that given a range $[i,j]$, we can return a representation of a shortes

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::904f48fbc81b6de749398a96836f8886
https://inria.hal.science/hal-03498358/file/2106.01763.pdf