Internal shortest absent word queries in constant time and linear space

Golnaz Badkobeh; Panagiotis Charalampopoulos; Dmitry Kosolobov; Solon P. Pissis

doi:10.1016/j.tcs.2022.04.029

Internal shortest absent word queries in constant time and linear space

Golnaz Badkobeh, Panagiotis Charalampopoulos, Dmitry Kosolobov^*, Solon P. Pissis

^*Corresponding author for this work

Research output: Contribution to Journal › Article › Academic › peer-review

88 Downloads (Pure)

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.

Original language	English
Pages (from-to)	271-282
Number of pages	12
Journal	Theoretical Computer Science
Volume	922
Early online date	26 Apr 2022
DOIs	https://doi.org/10.1016/j.tcs.2022.04.029
Publication status	Published - 24 Jun 2022

Bibliographical note

Funding Information:
Supported by the Israel Science Foundation grants 592/17 and 810/21.Supported by the Ministry of Science and Higher Education of the Russian Federation (Ural Mathematical Center project No. 075-02-2022-877).Supported by the ALPACA and PANGAIA projects that have received funding from the European Union's Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreements no. 956229 and no. 872539.

Publisher Copyright:
© 2022 Elsevier B.V.

Funding

Supported by the Israel Science Foundation grants 592/17 and 810/21.Supported by the Ministry of Science and Higher Education of the Russian Federation (Ural Mathematical Center project No. 075-02-2022-877).Supported by the ALPACA and PANGAIA projects that have received funding from the European Union's Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreements no. 956229 and no. 872539.

Funders	Funder number
Horizon 2020 Framework Programme
Ministry of Education and Science of the Russian Federation
ALPACA
Horizon 2020
Ural Mathematical Center	075-02-2022-877
Israel Science Foundation	592/17, 810/21
H2020 Marie Skłodowska-Curie Actions	872539, 956229

Keywords

Bit parallelism
Internal queries
Shortest absent word
String algorithms

UN SDGs

This output contributes to the following UN Sustainable Development Goals (SDGs)

Access to Document

10.1016/j.tcs.2022.04.029

Internal shortest absent word queries in constant time and linear spaceFinal published version, 468 KBLicence: Article 25fa Dutch Copyright Act

Persistent URL (handle)

Persistent link

Cite this

@article{ed3be6f7164c4b5eac9c0a6c5d697b53,

title = "Internal shortest absent word queries in constant time and linear space",

abstract = "Given a string T of length n over an alphabet Σ⊂\{1,2,…,nO(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.",

keywords = "Bit parallelism, Internal queries, Shortest absent word, String algorithms",

author = "Golnaz Badkobeh and Panagiotis Charalampopoulos and Dmitry Kosolobov and Pissis, \{Solon P.\}",

note = "Funding Information: Supported by the Israel Science Foundation grants 592/17 and 810/21.Supported by the Ministry of Science and Higher Education of the Russian Federation (Ural Mathematical Center project No. 075-02-2022-877).Supported by the ALPACA and PANGAIA projects that have received funding from the European Union's Horizon 2020 research and innovation programme under the Marie Sk{\l}odowska-Curie grant agreements no. 956229 and no. 872539. Publisher Copyright: {\textcopyright} 2022 Elsevier B.V.",

year = "2022",

month = jun,

day = "24",

doi = "10.1016/j.tcs.2022.04.029",

language = "English",

volume = "922",

pages = "271--282",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier B.V.",

}

TY - JOUR

T1 - Internal shortest absent word queries in constant time and linear space

AU - Badkobeh, Golnaz

AU - Charalampopoulos, Panagiotis

AU - Kosolobov, Dmitry

AU - Pissis, Solon P.

N1 - Funding Information: Supported by the Israel Science Foundation grants 592/17 and 810/21.Supported by the Ministry of Science and Higher Education of the Russian Federation (Ural Mathematical Center project No. 075-02-2022-877).Supported by the ALPACA and PANGAIA projects that have received funding from the European Union's Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreements no. 956229 and no. 872539. Publisher Copyright: © 2022 Elsevier B.V.

PY - 2022/6/24

Y1 - 2022/6/24

N2 - Given a string T of length n over an alphabet Σ⊂{1,2,…,nO(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.

AB - Given a string T of length n over an alphabet Σ⊂{1,2,…,nO(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.

KW - Bit parallelism

KW - Internal queries

KW - Shortest absent word

KW - String algorithms

UR - https://www.scopus.com/pages/publications/85129567862

UR - https://www.scopus.com/inward/citedby.url?scp=85129567862&partnerID=8YFLogxK

U2 - 10.1016/j.tcs.2022.04.029

DO - 10.1016/j.tcs.2022.04.029

M3 - Article

AN - SCOPUS:85129567862

SN - 0304-3975

VL - 922

SP - 271

EP - 282

JO - Theoretical Computer Science

JF - Theoretical Computer Science

ER -

Internal shortest absent word queries in constant time and linear space

Abstract

Bibliographical note

Funding

Keywords

UN SDGs

Access to Document

Persistent URL (handle)

Other files and links

Fingerprint

Cite this