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 language | English |
|---|---|
| Title of host publication | 32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021) |
| Editors | Pawel Gawrychowski, Tatiana Starikovskaya |
| Publisher | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |
| Pages | 1-18 |
| Number of pages | 18 |
| ISBN (Print) | 9783959771863 |
| DOIs | |
| Publication status | Published - 2021 |
| Event | 32nd Annual Symposium on Combinatorial Pattern Matching, CPM 2021 - Wroclaw, Poland Duration: 5 Jul 2021 → 7 Jul 2021 |
Publication series
| Name | Leibniz International Proceedings in Informatics, LIPIcs |
|---|---|
| Volume | 191 |
| ISSN (Print) | 1868-8969 |
Conference
| Conference | 32nd Annual Symposium on Combinatorial Pattern Matching, CPM 2021 |
|---|---|
| Country/Territory | Poland |
| City | Wroclaw |
| Period | 5/07/21 → 7/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