Dictionary Matching With A Bounded Gap In Pattern Or In Text

A gap is a sequence of don’t care characters. In this paper, we study two variants of the dictionary matching problem, where gaps may be present in the patterns or in the text. The first variant, called dictionary matching with one gap, considers indexing a collection D of d one-gap-patterns, where the ith pattern is of the form Pi[ αi, βi] Qi with Pi and Qi are strings drawn from an alphabet Σ and [ αi, βi] denote the lower and upper bounds on the gap length. The target is to allow a user to efficiently identify all substrings of a query text T that match with any one-gap-pattern in the collection. We present a linear space solution for answering the above dictionary matching query in time O(| T| γlog λlog d+ occ) , where γ denotes the number of distinct gap lengths, λ denotes the number of distinct lower and upper bounds of gap lengths, and the occ is the output size. The query time can be improved to O(| T| γ+ occ) using O(d1+ϵ) extra space, where ϵ\u3e 0 is an arbitrarily small constant. Additionally, we show a succinct-space index offering a space–time tradeoff. In the special case where parameters αi and βi’s for all the patterns are same, our results improve upon the work by Amir et al. (Proceedings of annual symposium on combinatorial pattern matching (CPM), 2014, Theor Comput Sci 589:34–46, 2015). The second variant, called dictionary matching with one missing substring, is a new problem in which a gap of bounded length may be present in the text substring when it is being matched. We show that this problem can be solved by using a similar framework. Furthermore, by applying a centroid path decomposition on the failure tree, we obtain a space–time tradeoff result, which will be suitable when the dictionary contains only short patterns, or when index space is a critical concern