Internal Shortest Absent Word Queries in Constant Time and Linear Space - Archive ouverte HAL Access content directly
Conference Papers Year :

Internal Shortest Absent Word Queries in Constant Time and Linear Space

(1) , (2) , (3) , (4, 5, 6)
1
2
3
4
5
6

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(n log σ n) time.
Fichier principal
Vignette du fichier
2106.01763.pdf (519.1 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

hal-03498358 , version 1 (21-12-2021)

Identifiers

  • HAL Id : hal-03498358 , version 1

Cite

Golnaz Badkobeh, Panagiotis Charalampopoulos, Dmitry Kosolobov, Solon P Pissis. Internal Shortest Absent Word Queries in Constant Time and Linear Space. CPM 2021 - 32nd Annual Symposium on Combinatorial Pattern Matching, Jul 2021, Wroclaw, Poland. pp.1-13. ⟨hal-03498358⟩

Collections

INRIA INRIA2
10 View
38 Download

Share

Gmail Facebook Twitter LinkedIn More