← 研踪 PaperTrailarXiv:2611.04852 · v1
Faster Regular Expression Matching via Two-Dimensional Tabulation
首次提交 2026-11-03 21:16
版本更新 2026-11-03 21:16
雷达观测 2026-11-04 23:39
摘要
Regular expression matching asks whether a string of length $n$ belongs to the language described by a regular expression of length $m$. We give an algorithm that solves this problem in linear space and $O(nm \log \log n/\log^2 n + n + m)$ time. This improves the leading term of the previous best worst-case constant-alphabet time bound by a factor of $\sqrt{\log n}$. The key new technique is a two-dimensional tabulation specialized to the regular expression.
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-03 21:16 · 最新观测版本
Faster Regular Expression Matching via Two-Dimensional Tabulation
Regular expression matching asks whether a string of length $n$ belongs to the language described by a regular expression of length $m$. We give an algorithm that solves this problem in linear space and $O(nm \log \log n/\log^2 n + n + m)$ time. This improves the leading term of the previous best worst-case constant-alphabet time bound by a factor of $\sqrt{\log n}$. The key new technique is a two-dimensional tabulation specialized to the regular expression.
查看此版本解读 →查看此版本原文 ↗