Abstract
Dictionary matching is a well-studied problem in computer sci- ence, which have found numerous applications, such as computer virus detection and bioinformatics analysis. In this thesis, we study three variants of the dictionary matching problem. The first variant, called dictionary matching with gapped patterns, is recently proposed by Amir et al. in which a pattern may be matched with a substring of a query text T with a gap of bounded length present in the pattern. We first give an alter- native linear-space solution to Amir et al.’s problem, where gap lengths of all patterns have the same lower bound α and upper bound β. The query time on any query text T is bounded by O((β − α + 1)|T | log d + occ), where d denotes the number of patterns, and occ denotes the size of the output. After that, we show that the framework can be generalized to handle the case where gaps may have different bounds, thereby answering one of the open problems raised by Amir et al. 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 prob- lem can be solved by using a similar framework. Furthermore, by applying a novel indexing technique 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. The third variant is called parameterized dictionary matching. Idury et al. proposed a linear-space so- lution for this problem using Baker’s encoding method. Here, we come up with a new encoding method, which allows us to achieve a better space complexity for the index, with only slight slowdown in the query time.