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.
Categories: cs.DS
