Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2020 | 10.1007/978-3-030-59212-7_5 | SPIRE |
DocType | Citations | PageRank |
Conference | 0 | 0.34 |
References | Authors | |
0 | 7 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Maxime Crochemore | 1 | 2655 | 281.75 |
| Costas Iliopoulos | 2 | 0 | 0.34 |
| Jakub Radoszewski | 3 | 624 | 50.36 |
| Wojciech Rytter | 4 | 2290 | 181.52 |
| Juliusz Straszynski | 5 | 2 | 5.15 |
| Tomasz Waleń | 6 | 706 | 39.62 |
| Wiktor Zuba | 7 | 1 | 5.13 |