Internal Shortest Absent Word Queries in Constant Time and Linear Space

Autor:	Badkobeh, Golnaz, Charalampopoulos, Panagiotis, Kosolobov, Dmitry, Pissis, Solon P.
Rok vydání:	2021
Předmět:	Computer Science - Data Structures and Algorithms
Druh dokumentu:	Working Paper
Popis:	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 shortest string over $\Sigma$ that is absent in the fragment $T[i]\cdots 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(n\log_\sigma n)$ time. Comment: 13 pages, 1 figure, 4 tables
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2106.01763 Zobrazit plný text záznamu View this record from Arxiv