Пожалуйста, используйте этот идентификатор, чтобы цитировать или ссылаться на этот ресурс:
http://elar.urfu.ru/handle/10995/117865
Название: | Internal shortest absent word queries in constant time and linear space |
Авторы: | Badkobeh, G. Charalampopoulos, P. Kosolobov, D. Pissis, S. P. |
Дата публикации: | 2022 |
Библиографическое описание: | Internal shortest absent word queries in constant time and linear space / G. Badkobeh, P. Charalampopoulos, D. Kosolobov et al. // Theoretical Computer Science. — 2022. — Vol. 922. — P. 271-282. |
Аннотация: | 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. © 2022 Elsevier B.V. |
Ключевые слова: | BIT PARALLELISM INTERNAL QUERIES SHORTEST ABSENT WORD STRING ALGORITHMS BIT PARALLELISM CONSTANT TIME INTERNAL QUERY INTERNAL SHORTS LINEAR SPACES PREPROCESS SHORT ABSENT WORD SPACE DATA STRUCTURES STRING ALGORITHMS TIME-SPACE COMPUTATIONAL METHODS |
URI: | http://elar.urfu.ru/handle/10995/117865 |
Условия доступа: | info:eu-repo/semantics/openAccess |
Идентификатор SCOPUS: | 85129567862 |
Идентификатор WOS: | 000850360300021 |
Идентификатор PURE: | 30538891 |
DOI: | 10.1016/j.tcs.2022.04.029 |
Сведения о поддержке: | 075-02-2022-877; H2020 Marie Skłodowska-Curie Actions, MSCA: 872539, 956229; Ministry of Education and Science of the Russian Federation, Minobrnauka; Israel Science Foundation, ISF: 592/17, 810/21; Horizon 2020 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. |
Располагается в коллекциях: | Научные публикации ученых УрФУ, проиндексированные в SCOPUS и WoS CC |
Файлы этого ресурса:
Файл | Описание | Размер | Формат | |
---|---|---|---|---|
2-s2.0-85129567862.pdf | 522,99 kB | Adobe PDF | Просмотреть/Открыть |
Все ресурсы в архиве электронных ресурсов защищены авторским правом, все права сохранены.