Name
Abstract | ||
|---|---|---|
We introduce data structures answering queries concerning the occurrences of patterns from a given dictionary D in fragments of a given string T of length n. The dictionary is internal in the sense that each pattern in D is given as a fragment of T. This way, D takes space proportional to the number of patterns d = vertical bar D vertical bar rather than their total length, which could be Theta(n . d). In particular, we consider the following types of queries: reporting and counting all occurrences of patterns from D in a fragment T [i .. j] and reporting distinct patterns from D that occur in T [i .. j]. We show how to construct, in O((n + d) log(O(1)) n) time, a data structure that answers each of these queries in time O(log(O(1)) n + vertical bar output vertical bar). 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 |
|---|---|---|
2021 | 10.1007/s00453-021-00821-y | ALGORITHMICA |
Keywords | DocType | Volume |
Dictionary matching, Internal pattern matching, Range searching, Dynamic dictionary | Journal | 83 |
Issue | ISSN | Citations |
7 | 0178-4617 | 0 |
PageRank | References | Authors |
0.34 | 0 | 6 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Panagiotis Charalampopoulos | 1 | 29 | 9.41 |
| Tomasz Kociumaka | 2 | 217 | 38.57 |
| Manal Mohamed | 3 | 1 | 0.70 |
| Jakub Radoszewski | 4 | 624 | 50.36 |
| wojciech rytter | 5 | 130 | 17.13 |
| Tomasz Waleń | 6 | 706 | 39.62 |