Near-Optimal Property Testers for Pattern Matching

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, that is, $P= T[i. . i+m)$ holds for some $i \in[0. . n-m]$. A property tester for the problem needs to distinguish (with high probability) the following two cases for some threshold $k \in[1. . m)$: the Yes case, where P occurs as a substring of T, and the No case, where $\boldsymbol{P}$ has Hamming distance greater than k from every substring of T, that is, P has no k-mismatch occurrence in T. In this work, we provide adaptive and non-adaptive property testers for the exact pattern matching problem, jointly covering the whole spectrum of parameters. We further establish unconditional lower bounds demonstrating that the time and query complexities of our algorithms are optimal, up to polylog n factors hidden within the $\widetilde{\mathcal{O}}(\cdot)$ notation below. In the most studied regime of $n=m+\Theta(m)$, our nonadaptive property tester has the time complexity of $\widetilde{\mathcal{O}}(n / \sqrt{k})$, and a matching lower bound remains valid for the query complexity of adaptive algorithms. This improves both upon a folklore solution that attains the optimal query complexity but requires $\Omega(n)$ time, and upon the only previously known sublineartime property tester, by Chan, Golan, Kociumaka, Kopelowitz, and Porat [STOC 2020], with time complexity $\widetilde{\mathcal{O}}(n / \sqrt[3]{k})$. The aforementioned results remain valid for $n=m+\Omega(m)$, where our optimal running time $\widetilde{\mathcal{O}}(\sqrt{n m / k}+n / k)$ improves upon the previously best time complexity of $\mathcal{O}\left(\sqrt[3]{n^{2} m / k}+n / k\right)$. In the regime of $n=m+o(m)$, which has not been targeted in any previous work, we establish a surprising separation between adaptive and non-adaptive algorithms, whose optimal time and query complexities are $\widetilde{\mathcal{O}}(\sqrt{(n-m+1) m / k}+n / k)$ and $\widetilde{\mathcal{O}}(\min (n \sqrt{n-m+1} / k, \sqrt{n m / k}+n / k))$, respectively. Our non-adaptive algorithms answer Yes with high probability not only when P has an exact occurrence in T but also when P has an occurrence with at most $k^{\prime}=\Omega(k / \log n)$ mismatches. The gap $k / k^{\prime}$ can be reduced by slightly increasing the running time; an arbitrarily small polynomial overhead already suffices to achieve a constant gap. Moreover, upon request, our algorithms may output a set $A \subseteq[0. . n-m]$ that contains the starting positions of all $\boldsymbol{k}^{\prime}$-mismatch occurrences of $\boldsymbol{P}$ in $\boldsymbol{T}$ and no starting position of an occurrence with more than k mismatches. The key technical innovation behind all our property testers is a novel characterization of the mismatches between the pattern P and the fragments $T[i . . i+m)$ across $i \in[0. . n-m]$. We show that one can select $\widetilde{\mathcal{O}}(k \cdot n / m)$ positions within P and T so that, for every $i \in[0. . n-m]$, at least $\min \left(k, k_{i}\right)$ of the $k_{i}$ mismatches between P and $T[i .. i+m)$ involve a selected position. Previously, such a construction was known for k