Internal shortest absent word queries

Golnaz Badkobeh*, Panagiotis Charalampopoulos, Solon P. Pissis

*Corresponding author for this work

Research output: Chapter in Book / Report / Conference proceedingConference contributionAcademicpeer-review

Abstract

Given a string T of length n over an alphabet Σ ⊂ {1, 2, . . ., nO(1)} of size s, 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. For any positive integer k ϵ [1, log logσ n], we present an O((n/k) · log logσ n)-size data structure, which can be constructed in O(n logs n) time, and answers queries in time O(log logσ k).

Original languageEnglish
Title of host publication32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021)
EditorsPawel Gawrychowski, Tatiana Starikovskaya
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Pages1-18
Number of pages18
ISBN (Print)9783959771863
DOIs
Publication statusPublished - 2021
Event32nd Annual Symposium on Combinatorial Pattern Matching, CPM 2021 - Wroclaw, Poland
Duration: 5 Jul 20217 Jul 2021

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume191
ISSN (Print)1868-8969

Conference

Conference32nd Annual Symposium on Combinatorial Pattern Matching, CPM 2021
Country/TerritoryPoland
CityWroclaw
Period5/07/217/07/21

Bibliographical note

Funding Information:
Supported by the Israel Science Foundation grant 592/17.

Publisher Copyright:
© Golnaz Badkobeh, Panagiotis Charalampopoulos, and Solon P. Pissis.

Keywords

  • Bit parallelism
  • Internal queries
  • Shortest absent word
  • String algorithms

Fingerprint

Dive into the research topics of 'Internal shortest absent word queries'. Together they form a unique fingerprint.

Cite this