Near-Optimal Property Testers for Pattern Matching

Ce Jin, Tomasz Kociumaka

The classic exact pattern matching problem, given two strings -- a pattern $P$ of length $m$ and a text $T$ of length $n$ -- asks whether $P$ occurs as a substring of $T$. A proper…