Internal Shortest Absent Word Queries in Constant Time and Linear Space

Given a string $T$ of length $n$ over an alphabet $Sigmasubset {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(nlog_sigma n)$ time.