Reporting consecutive substring occurrences under bounded gap constraints
| Author | dc.contributor.author | Navarro, Gonzalo | |
| Author | dc.contributor.author | Thankachan, Sharma V. | |
| Admission date | dc.date.accessioned | 2016-12-07T15:46:20Z | |
| Available date | dc.date.available | 2016-12-07T15:46:20Z | |
| Publication date | dc.date.issued | 2016 | |
| Cita de ítem | dc.identifier.citation | Theoretical Computer Science 638 (2016) 108–111 | es_ES |
| Identifier | dc.identifier.other | 10.1016/j.tcs.2016.02.005 | |
| Identifier | dc.identifier.uri | https://repositorio.uchile.cl/handle/2250/141730 | |
| Abstract | dc.description.abstract | We study the problem of indexing a text T[1...n] such that whenever a pattern P[1...p] and an interval [alpha, beta] come as a query, we can report all pairs (i, j) of consecutive occurrences of P in T with alpha <= j - i <= beta. We present an O (n logn) space data structure with optimal O (p + k) query time, where k is the output size. | es_ES |
| Patrocinador | dc.description.sponsorship | Basal Funds, CONICYT, Chile FB0001 | es_ES |
| Lenguage | dc.language.iso | en | es_ES |
| Publisher | dc.publisher | Elsevier | es_ES |
| Type of license | dc.rights | Attribution-NonCommercial-NoDerivs 3.0 Chile | * |
| Link to License | dc.rights.uri | http://creativecommons.org/licenses/by-nc-nd/3.0/cl/ | * |
| Source | dc.source | Theoretical Computer Science | es_ES |
| Keywords | dc.subject | Suffix trees | es_ES |
| Keywords | dc.subject | Geometric data structures | es_ES |
| Keywords | dc.subject | Heavy-path decomposition | es_ES |
| Keywords | dc.subject | Pattern matching | es_ES |
| Título | dc.title | Reporting consecutive substring occurrences under bounded gap constraints | es_ES |
| Document type | dc.type | Artículo de revista | |
| Cataloguer | uchile.catalogador | laj | es_ES |
| Indexation | uchile.index | Artículo de publicación ISI | es_ES |
Files in this item
This item appears in the following Collection(s)
-
Artículos de revistas
Artículos de revistas
Except where otherwise noted, this item's license is described as Attribution-NonCommercial-NoDerivs 3.0 Chile