A regular expression $R$ consists of single characters combined with concatenation, union and Kleene star operators, defining a set of strings. Given $R$ of length $m$ and a query string $Q$ of length $n$, the matching problem asks whether $Q$ belongs to the language of $R$. We present a two‑dimensional tabulation algorithm parameterized by $t \ge m$ with time complexity $$ O\left(\frac{nm\,\lg\lg(t/m)}{\lg^2(t/m)}+t+n\right) $$ and $O(t)$ words of space. When $t$ is chosen as $\Theta(m\log m)$ the bound becomes $O\bigl(nm / \log m\bigr)$, improving over the classic $O(nm)$ dynamic programming approach. The key idea maps matching states onto a $[0,m]\times[0,n]$ grid and applies block decomposition so that each block can be processed in near‑constant time. The implementation proceeds by splitting $R$ into sub‑expressions of length at most $t/m$, building local transition tables for each sub‑expression with double‑logarithmic lookup, and merging these tables to obtain the final result. Experiments on randomly generated expressions and real‑world texts show average speedups of 2–3×, and the technique extends to regexes with capture groups with only modest extra space.
Review