Consecutive Occurrences with Distance Constraints

A consecutive occurrence of a pattern P[1 : m] in a text T[1 : n] is a pair (i, j), with \(i<j_ _="" of="" indices="" in="" T="" such="" that="" P="" occurs="" at="" i="" and="" j_="" but="" not="" any="" index="" between="" them.="" We="" give="" deterministic="" solutions="" to="" the="" following="" two="" problems="" using="" simple="" classical="" data="" structures.="" The="" first="" problem="" is="" preprocess="" text="" so="" one="" can="" efficiently="" answer="" bounded="" gap="" queries:="" _given="" a="" pattern="" range="" _alpha="" _beta="" _="" _1_le="" _alpha="" _le="" n_="" report="" all="" consecutive="" occurrences="" _i_j_="" with="" distance="" _j-i="" _in="" _alpha="" _beta="" _="" _.="" present="" an="" _O_n_log="" n_="" structure="" supports="" queries="" _O_m="" _="" _log="" _output_="" time="" needed="" build="" _O_n_2_="" Moreover_="" query="" be="" improved="" if="" _alpha="" or="" _beta="" known="" preprocessing.="" second="" string="" indexing="" for="" top-k="" close="" problem_="" which="" asks="" input="" T_1_:_n_="" quickly="" integer="" _k="">0\) and a pattern P, report the k closest consecutive occurrences of P in T”. Using the same data structure mentioned above, we can answer a top-k query in \(O(m + \#output)\) -time.