Nearly Optimal Internal Dictionary Matching

Jingbang Chen, Jiangqi Dai, Qiuyang Mang +2

We study the internal dictionary matching (IDM) problem where a dictionary $\mathcal{D}$ containing $d$ substrings of a text $T$ is given, and each query concerns the occurrences o…