正则表达式 $R$ 由单字符、连接、并集和 Kleene 星号构成，定义了一族字符串。给定正则表达式 $R$（长度 $m$）和查询字符串 $Q$（长度 $n$），匹配问题是判定 $Q$ 是否属于 $R$ 所描述的集合。我们提出一种基于二维表格的算法，使用参数 $t \ge m$，其时间复杂度为 $$ O\left(\frac{nm\,\lg\lg(t/m)}{\lg^2(t/m)}+t+n\right) $$ 空间复杂度为 $O(t)$ 字。该算法在 $t$ 取 $\Theta(m\log m)$ 时得到 $O\bigl(nm / \log m\bigr)$ 的时间，上界优于传统的 $O(nm)$ 动态规划。核心思想是将匹配状态映射到 $[0,m]\times[0,n]$ 的二维网格，并利用分块技术在每块内部实现近似常数时间的转移。实现步骤包括：将正则表达式拆分为若干子表达式，使每个子表达式长度不超过 $t/m$；对每个子表达式构建局部转移表，使用双层对数加速查找；通过合并子表得到全局匹配结果。实验在随机生成的正则表达式和真实文本上验证，平均加速比可达 2–3 倍，且该方法同样适用于带有捕获组的扩展正则，只需少量额外空间即可实现。
点评