Mind the Gap

Amihood Amir, Tsvi Kopelowitz, Avivit Levy +3

We examine the complexity of the online Dictionary Matching with One Gap Problem (DMOG) which is the following. Preprocess a dictionary $D$ of $d$ patterns, where each pattern cont…