Internal Shortest Absent Word Queries in Constant Time and Linear Space

2021/06/03 by Golnaz Badkobeh, Panagiotis Charalampopoulos, Badkobeh, Golnaz +5
Computer Science · #Algorithms and Data Compression #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Natural Language Processing Techniques #Network Packet Processing and Optimization

paper · doi:10.48550/arxiv.2106.01763

openalex publication_date 2021/06/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Given a string T of length n over an alphabet Σ⊂ \1,2,…,n^O(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. We present an O(n)-space data structure that answers such queries in constant time and can be constructed in O(nlog_σn) time.

Related

• Minimal Absent Words on Run-Length Encoded Strings
• Linear-time computation of generalized minimal absent words for multiple strings
• Efficiently Finding All Minimal and Shortest Absent Subsequences in a String
• Computing Minimal Absent Words and Extended Bispecial Factors with CDAWG Space
• A Simple Linear-Space Data Structure for Constant-Time Range Minimum Query