Dictionary Matching with One Gap

Amihood Amir, Avivit Levy, Ely Porat +1

The dictionary matching with gaps problem is to preprocess a dictionary $D$ of $d$ gapped patterns $P_1,\dots ,P_d$ over alphabet $\Sigma$, where each gapped pattern $P_i$ is a sequence…