Internal shortest absent word queries in constant time and linear space
| Autor: | Golnaz Badkobeh, Panagiotis Charalampopoulos, Dmitry Kosolobov, Solon P. Pissis |
|---|---|
| Přispěvatelé: | Goldsmiths, University of London (Goldsmiths College), University of London [London], Interdisciplinary Center Herzliya (IDC), Ural Federal University [Ekaterinburg] (UrFU), Centrum Wiskunde & Informatica (CWI), Vrije Universiteit Amsterdam [Amsterdam] (VU), Equipe de recherche européenne en algorithmique et biologie formelle et expérimentale (ERABLE), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Department of Computing, Goldsmiths, University of London, The Interdisciplinary Center Herzliya, Israel, Bioinformatics, AIMMS, Bio Informatics (IBIVU), Centrum Wiskunde & Informatica, Amsterdam (CWI), The Netherlands |
| Jazyk: | angličtina |
| Rok vydání: | 2021 |
| Předmět: |
FOS: Computer and information sciences
String algorithms CONSTANT TIME General Computer Science INTERNAL SHORTS INTERNAL QUERY Internal queries TIME-SPACE Theoretical Computer Science PREPROCESS Computer Science - Data Structures and Algorithms Data Structures and Algorithms (cs.DS) [INFO]Computer Science [cs] Computer Science::Databases Shortest absent word SHORT ABSENT WORD Bit parallelism LINEAR SPACES internal queries string algorithms SPACE DATA STRUCTURES COMPUTATIONAL METHODS bit parallelism shortest absent word SDG 4 - Quality Education |
| Zdroj: | 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 |
| ISSN: | 0304-3975 |
| DOI: | 10.1016/j.tcs.2022.04.029 |
| Popis: | 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 shortest string over $\Sigma$ that is absent in the fragment $T[i]\cdots 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_\sigma n)$ time. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect