Internal shortest absent word queries
| Autor: | Badkobeh, Golnaz, Charalampopoulos, Panagiotis, Pissis, Solon P., Gawrychowski, Pawel, Starikovskaya, Tatiana |
|---|---|
| Přispěvatelé: | Gawrychowski, Pawel, Starikovskaya, Tatiana, Bioinformatics, AIMMS, Bio Informatics (IBIVU) |
| Jazyk: | angličtina |
| Rok vydání: | 2021 |
| Předmět: | |
| Zdroj: | 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) |
| DOI: | 10.4230/lipics.cpm.2021.6 |
| Popis: | 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. For any positive integer k ∈ [1,log log_σ n], we present an 𝒪((n/k)⋅ log log_σ n)-size data structure, which can be constructed in 𝒪(nlog_σ n) time, and answers queries in time 𝒪(log log_σ k). LIPIcs, Vol. 191, 32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021), pages 6:1-6:18 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|