摘要
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 (Formula presented.) of d one-gap-patterns, where the ith pattern is of the form (Formula presented.) with (Formula presented.) and (Formula presented.) are strings drawn from an alphabet (Formula presented.) and (Formula presented.) 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 (Formula presented.), where (Formula presented.) denotes the number of distinct gap lengths, (Formula presented.) denotes the number of distinct lower and upper bounds of gap lengths, and the (Formula presented.) is the output size. The query time can be improved to (Formula presented.) using (Formula presented.) extra space, where (Formula presented.) is an arbitrarily small constant. Additionally, we show a succinct-space index offering a space–time tradeoff. In the special case where parameters (Formula presented.) and (Formula presented.)’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.