Name
Abstract | ||
|---|---|---|
We consider the problem of preprocessing a text $T$ of length $n$ and a dictionary $\mathcal{D}$ in order to be able to efficiently answer queries $CountDistinct(i,j)$, that is, given $i$ and $j$ return the number of patterns from $\mathcal{D}$ that occur in the fragment $T[i \mathinner{.\,.} j]$. The dictionary is internal in the sense that each pattern in $\mathcal{D}$ is given as a fragment of $T$. This way, the dictionary takes space proportional to the number of patterns $d=|\mathcal{D}|$ rather than their total length, which could be $\Theta(n\cdot d)$. An $\tilde{\mathcal{O}}(n+d)$-size data structure that answers $CountDistinct(i,j)$ queries $\mathcal{O}(\log n)$-approximately in $\tilde{\mathcal{O}}(1)$ time was recently proposed in a work that introduced internal dictionary matching [ISAAC 2019]. Here we present an $\tilde{\mathcal{O}}(n+d)$-size data structure that answers $CountDistinct(i,j)$ queries $2$-approximately in $\tilde{\mathcal{O}}(1)$ time. Using range queries, for any $m$, we give an $\tilde{\mathcal{O}}(\min(nd/m,n^2/m^2)+d)$-size data structure that answers $CountDistinct(i,j)$ queries exactly in $\tilde{\mathcal{O}}(m)$ time. We also consider the special case when the dictionary consists of all square factors of the string. We design an $\mathcal{O}(n \log^2 n)$-size data structure that allows us to count distinct squares in a text fragment $T[i \mathinner{.\,.} j]$ in $\mathcal{O}(\log n)$ time. |
Year | DOI | Venue |
|---|---|---|
2020 | 10.4230/LIPIcs.CPM.2020.8 | CPM |
DocType | Citations | PageRank |
Conference | 0 | 0.34 |
References | Authors | |
0 | 8 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Charalampopoulos Panagiotis | 1 | 0 | 0.68 |
| Tomasz Kociumaka | 2 | 217 | 38.57 |
| Manal Mohamed | 3 | 102 | 12.62 |
| Jakub Radoszewski | 4 | 624 | 50.36 |
| Wojciech Rytter | 5 | 2290 | 181.52 |
| Straszyński Juliusz | 6 | 0 | 0.34 |
| Tomasz Waleń | 7 | 706 | 39.62 |
| Zuba Wiktor | 8 | 0 | 0.34 |