Fast and linear-time string matching algorithms based on the distances of $q$-gram occurrences

Satoshi Kobayashi, Diptarama Hendrian, Ryo Yoshinaka +1

Given a text $T$ of length $n$ and a pattern $P$ of length $m$, the string matching problem is a task to find all occurrences of $P$ in $T$. In this study, we propose an algorithm…