تقرير
Internal Quasiperiod Queries
| العنوان: | Internal Quasiperiod Queries |
|---|---|
| المؤلفون: | Crochemore, Maxime, Iliopoulos, Costas, Radoszewski, Jakub, Rytter, Wojciech, Straszyński, Juliusz, Waleń, Tomasz, Zuba, Wiktor |
| سنة النشر: | 2020 |
| المجموعة: | Computer Science |
| مصطلحات موضوعية: | Computer Science - Data Structures and Algorithms |
| الوصف: | 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. Comment: To appear in the SPIRE 2020 proceedings |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2007.13471 |
| رقم الأكسشن: | edsarx.2007.13471 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |