Bookmark Saya

arXiv Open Access 2020

Internal Quasiperiod Queries

Maxime Crochemore Costas Iliopoulos Jakub Radoszewski Wojciech Rytter Juliusz Straszyński +2 lainnya
Lihat Sumber

Abstrak

Internal pattern matching requires one to answer queries about factors of a given string. Many results are known on answering internal period queries, asking for the periods of a given factor. In this paper we investigate (for the first time) internal queries asking for covers (also known as quasiperiods) of a given factor. We propose a data structure that answers such queries in $O(\log n \log \log n)$ time for the shortest cover and in $O(\log n (\log \log n)^2)$ time for a representation of all the covers, after $O(n \log n)$ time and space preprocessing.

Topik & Kata Kunci

cs.DS

Penulis (7)

M

Maxime Crochemore

C

Costas Iliopoulos

J

Jakub Radoszewski

W

Wojciech Rytter

J

Juliusz Straszyński

T

Tomasz Waleń

W

Wiktor Zuba

Format Sitasi

APA MLA BibTeX
Crochemore, M., Iliopoulos, C., Radoszewski, J., Rytter, W., Straszyński, J., Waleń, T. et al. (2020). Internal Quasiperiod Queries. https://arxiv.org/abs/2007.13471

Akses Cepat

Lihat di Sumber
Informasi Jurnal
Tahun Terbit
2020
Bahasa
en
Sumber Database
arXiv
Akses
Open Access ✓