Abstract
A gap-pattern is a sequence of sub-patterns separated by bounded sequences of don’t care characters (called gaps). A one-gappattern is a pattern of the form P[α, β]Q, where P and Q are strings drawn from alphabet Σ and [α, β] are lower and upper bounds on the gap size g. The gap size g is the number of don’t care characters between P and Q. The dictionary matching problem with one-gap is to index a collection of one-gap-patterns, so as to identify all sub-strings of a query text T that match with any one-gap-pattern in the collection. Let D be such a collection of d patterns, where D = {P <sub>i</sub> [α <sub>i,</sub> β <sub>i</sub> ]Q <sub>i</sub> | 1 ≤ i ≤ d}. Let n = ∑ <sup>d</sup> <sub>i=1</sub> |P <sub>i</sub> | + |Q <sub>i</sub> |. Let γ and λ be two parameters defined on D as follows: γ = |{j | j ∈ [α <sub>i</sub> , β <sub>i</sub> ], 1 ≤ i ≤ d}| and λ = |{α <sub>i</sub> , β <sub>i</sub> | 1 ≤ i ≤ d}|. Specifically γ is the total number gap lengths possible over all patterns in D and λ is the number of distinct gap boundaries across all the patterns. We present a linear space solution (i.e., O(n) words) for answering a dictionary matching query on D in time O(|T|γ log λ log d + occ), where occ is the output size. The query time can be improved to O(|T|γ +occ) using O(n + d <sup>1+ϵ</sup> ) space, where ϵ > 0 is an arbitrarily small constant. Additionally, we show a compact/succinct space index offering a spacetime trade-off. In the special case where parameters α <sub>i</sub> and β <sub>i</sub> ’s for all the patterns are same, our results improve upon the work by Amir et al. [CPM, 2014]. We also explore several related cases where gaps can occur at arbitrary locations and where gap can be induced in the text rather than pattern.