Internal Shortest Absent Word Queries in Constant Time and Linear Space

Autor: Badkobeh, Golnaz, Charalampopoulos, Panagiotis, Kosolobov, Dmitry, Pissis, Solon P.

Given a string $T$ of length $n$ over an alphabet $\Sigma\subset \{1,2,\ldots,n^{O(1)}\}$ of size $\sigma$, we are to preprocess $T$ so that given a range $[i,j]$, we can return a representation of a shortest string over $\Sigma$ that is absent in th

Externí odkaz: http://arxiv.org/abs/2106.01763

Internal shortest absent word queries in constant time and linear space

Autor: Golnaz Badkobeh, Panagiotis Charalampopoulos, Dmitry Kosolobov, Solon P. Pissis

Publikováno v: CPM 2021-32nd Annual Symposium on Combinatorial Pattern Matching
CPM 2021-32nd Annual Symposium on Combinatorial Pattern Matching, Jul 2021, Wroclaw, Poland. pp.1-13
Badkobeh, G, Charalampopoulos, P, Kosolobov, D & Pissis, S P 2022, ' Internal shortest absent word queries in constant time and linear space ', Theoretical Computer Science, vol. 922, pp. 271-282 . https://doi.org/10.1016/j.tcs.2022.04.029
32nd Annual Symposium on Combinatorial Pattern Matching (CPM)
32nd Annual Symposium on Combinatorial Pattern Matching (CPM), 2021, Wroclaw, Poland
Theoretical Computer Science
Theoretical Computer Science, 922, 271-282. Elsevier
NARCIS
arXiv.org e-Print Archive
Hal-Diderot
Mémoires en Sciences de l'Information et de la Communication
Institutional repository of Ural Federal University named after the first President of Russia B.N.Yeltsin
Vrije Universiteit Amsterdam (VU Amsterdam)-Institutional Repository
INRIA a CCSD electronic archive server
Datacite
ORCID
Theoretical Computer Science, 922, 271-282

Comment: 13 pages, 1 figure, 4 tables
Given a string $T$ of length $n$ over an alphabet $\Sigma\subset \{1,2,\ldots,n^{O(1)}\}$ of size $\sigma$, we are to preprocess $T$ so that given a range $[i,j]$, we can return a representation of a shortes

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::904f48fbc81b6de749398a96836f8886
https://inria.hal.science/hal-03498358/file/2106.01763.pdf

Internal shortest absent word queries

Autor: Badkobeh, Golnaz, Charalampopoulos, Panagiotis, Pissis, Solon P., Gawrychowski, Pawel, Starikovskaya, Tatiana

Publikováno v: Badkobeh, G, Charalampopoulos, P & Pissis, S P 2021, Internal shortest absent word queries . in P Gawrychowski & T Starikovskaya (eds), 32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021) ., 6, Leibniz International Proceedings in Informatics, LIPIcs, vol. 191, Schloss Dagstuhl-Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, pp. 1-18, 32nd Annual Symposium on Combinatorial Pattern Matching, CPM 2021, Wroclaw, Poland, 5/07/21 . https://doi.org/10.4230/LIPIcs.CPM.2021.6
32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021), 1-18
STARTPAGE=1;ENDPAGE=18;TITLE=32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021)

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

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::146484f6d01978b95bfa68a77c70f7b3
https://doi.org/10.4230/lipics.cpm.2021.6

Tento výsledek nelze pro nepřihlášené uživatele zobrazit.
K zobrazení výsledku je třeba se přihlásit.

Absent Subsequences in Words.

Autor: Kosche, Maria¹ (AUTHOR) maria.kosche@cs.uni-goettingen.de, Koß, Tore¹ (AUTHOR) tore.koss@cs.uni-goettingen.de, Manea, Florin¹ (AUTHOR) florin.manea@cs.uni-goettingen.de, Siemer, Stefan¹ (AUTHOR) stefan.siemer@cs.uni-goettingen.de

Publikováno v: Fundamenta Informaticae. 2022, Vol. 189 Issue 3/4, p199-240. 42p.