Name
Abstract | ||
|---|---|---|
We introduce data structures answering queries concerning the occurrences of patterns from a given dictionary $\mathcal{D}$ in fragments of a given string $T$ of length $n$. The dictionary is internal in the sense that each pattern in $\mathcal{D}$ is given as a fragment of $T$. This way, $\mathcal{D}$ takes space proportional to the number of patterns $d=|\mathcal{D}|$ rather than their total length, which could be $\Theta(n\cdot d)$. In particular, we consider the following types of queries: reporting and counting all occurrences of patterns from $\mathcal{D}$ in a fragment $T[i..j]$ and reporting distinct patterns from $\mathcal{D}$ that occur in $T[i..j]$. We show how to construct, in $\mathcal{O}((n+d) \log^{\mathcal{O}(1)} n)$ time, a data structure that answers each of these queries in time $\mathcal{O}(\log^{\mathcal{O}(1)} n+|output|)$. The case of counting patterns is much more involved and needs a combination of a locally consistent parsing with orthogonal range searching. Reporting distinct patterns, on the other hand, uses the structure of maximal repetitions in strings. Finally, we provide tight---up to subpolynomial factors---upper and lower bounds for the case of a dynamic dictionary. |
Year | DOI | Venue |
|---|---|---|
2019 | 10.4230/LIPIcs.ISAAC.2019.22 | ISAAC |
DocType | Citations | PageRank |
Conference | 0 | 0.34 |
References | Authors | |
0 | 6 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Panagiotis Charalampopoulos | 1 | 3 | 4.12 |
| Tomasz Kociumaka | 2 | 217 | 38.57 |
| Manal Mohamed | 3 | 102 | 12.62 |
| Jakub Radoszewski | 4 | 624 | 50.36 |
| wojciech rytter | 5 | 130 | 17.13 |
| Tomasz Waleń | 6 | 706 | 39.62 |