Internal Shortest Absent Word Queries in Constant Time and Linear Space

Abstract

Given a string $T$ of length $n$ over an alphabet $\Sigma \subset \{1,2,\dots ,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.

13 pages, 1 figure, 4 tables