跳到正文
研踪PaperTrail

论文库

检索计算机领域论文,按研究方向、作者或关键词筛选。

部分采集异常
正在读取账号与研究记录…

全站更新概况

+197新增论文
+151其中 AI 相关
+16已有论文修订
+91新增 AI 导读

arXiv 最近完成扫描:2026-11-21 12:19 · 全站最近入库:2026-11-21 12:19各信源进度 →

统计口径与数据新鲜度

统计 2026-11-21 06:34 — 2026-11-22 06:34(北京时间) · 点击数字查看对应简报;AI 相关包含在新增论文内。

最近完成检查:2026-11-21 12:19最近发现新增版本:2026-11-21 12:19库内论文最新更新时间:2026-11-20 02:59

每分钟刷新已保存的数据。空检查不代表采集异常;新收录可能包含历史论文。AI 导读按新增版本计数。

29,158 已收录论文24,181 AI 相关8,992 有修订112 HF 社区发现

浏览论文库

时间范围跟随排序:版本更新、本站收录或首次发表。最新收录可能包含历史论文。部分信源异常,查看状态 →

找到 3 篇论文 · 按版本更新时间排序上轮扫描起点 2026-11-21 12:17(北京时间)
版本更新 · v2arXiv:2609.16914

Regular Expression Matching with Ordered Linear Backreferences

Philip Bille, Inge Li Gørtz, Rikke Schjeldrup Jessen

原文摘要

A regular expression with backreferences (rewb) specifies a set of strings formed by characters combined with concatenation, union, star operators, and backreferences. A backreference consists of a capturing group $(\cdot)_i$ and one or more references $\backslash i$. The substring matched by the reference must match the same substring that was matched by the corresponding capturing group. We focus on a subclass, which we call ordered linear rewbs where the references and capturing groups occur only outside star and union operators. Furthermore, we require that all references to a capturing group occur before the next capturing group in the rewb. In full generality, rewb matching is NP-complete, but efficient solutions exist for various subclasses. For linear rewbs with one capturing group and $k$ references, Uezato~[CPM 2026] gave an $O(k n^2 m^2)$ time and $O(n^2m^2)$ space algorithm, where $m$ is the length of the regular expression $R$ and $n$ is the length of the string $Q$. For the special case of $k=1$, Nogami and Terauchi~[MFCS 2025] gave an $O(n^2m^2)$ time and $O(n+ m^2)$ space algorithm. On the other hand, Nogami, Nakamura, and Terauchi~[arXiv 2026] gave a conditional lower bound, showing that we cannot solve the problem in $O(n^{2-ε} \mathrm{poly}(m))$ for any $ε> 0$ assuming the orthogonal vector hypothesis. Our main result is a new improved algorithm that runs in $O(n^2m+n^2k\log n)$ time and uses $O(nm)$ space, and handles the more general case of ordered linear rewbs with multiple capturing groups.

cs.DS

版本更新 · v2arXiv:2611.04852

Faster Regular Expression Matching via Two-Dimensional Tabulation

Philip Bille, Inge Li Gørtz

原文摘要

A regular expression specifies a set of strings formed by single characters combined with concatenation, union, and Kleene star operators. Given a regular expression $R$ and a string $Q$, the classic regular expression matching problem is to decide whether $Q$ matches any string specified by $R$. Let $m$ and $n$ be the lengths of $R$ and $Q$, respectively. Our main result is a new algorithm that, given a parameter $t \geq m$, solves the problem in \[ O\left(\frac{nm\,\lg\lg(t/m)}{\lg^2(t/m)}+t+n\right) \] time and $O(t)$ words of space. In particular, for any fixed $0<\eps<1$, when $m\leq n^{1-\eps}$, we solve the problem in $O(nm \lg \lg n/\lg^2 n + m + n)$ time and $O(n)$ space. Compared to the previous best result [Bille and Thorup, ICALP 2009], this improves the leading term by a factor $\sqrt{\lg n}/\lg\lg n$. The key new technique is a two-dimensional tabulation specialized to the regular expression.

cs.DS