# 一类四邻接网格图森林的匹配问题：路径分量的三次方上界

**历史研究记录（2026-10-12 更新）。** 一般三次方上界现已由[独立证明](cubic-bound.zh.md)解决。下文保留各阶段的推导、余项和反例；“尚未解决”指当时状态或该局部方法，更强的辅助命题不自动随一般上界成立。

本文分析[候选列表程序](../../std.cpp)，给出道路森林的每个分量都是路径时的自包含证明。证明由 Codex（GPT-6）整理。一般森林的分析见[主复杂度证明](../../complexity.zh.md)。

后续的[根叶路径证明](complexity-chains.zh.md)已把本子类的检查量改进为 $W\le(6n-5)N$，并覆盖道路可以分叉的路径查询。本文保留原有的方向字符串 border 证明及其独立引理。

## 结论与适用范围

设道路集合为 $F$，道路格数为 $N\le n^2$。如果道路森林的最大度数不超过 $2$，即每个分量都是路径或孤立点，则对任意输入行走序列都有

$$
\boxed{W\le(16n+1)N,\qquad
T=O(n^2+m+nN)\subseteq O(n^3+m),}
$$

其中 $W$ 为候选检查总数。

查询可以在已访问路径的两端交替延长，也可以在旧位移之间反复行走。若某次新增位移形成分支，就没有候选能够成功通过这一轮，因为道路路径不能容纳分支。

主复杂度证明中的独立水平条纹构造也属于这个子类。因此，当 $m\ge n-1$ 时，这个子类的最坏情况上下界已经合拢为 $\Theta(n^3+m)$。

## 方向字符串的 border 数量引理

把不重复经过顶点的网格路径编码为方向字符串 $w$，长度 $L$ 等于边数。一个非空字符串若同时是 $w$ 的前缀和后缀，就称为它的一个 **border（相等前后缀）**。这里把整个 $w$ 也计入 border，记数量为 $B(w)$。

**引理。** 如果这条路径可以平移放入 $n\times n$ 网格，那么

$$
B(w)\le4n.
$$

这个引理只要求路径没有重复顶点，不要求它是诱导路径。以下给出不依赖外部字符串定理的证明。

### 1. 最短周期与最长 border

整数 $p\in[1,L]$ 称为字符串的周期，如果所有有定义的位置均满足 $w_i=w_{i+p}$。设最短周期为 $p$，则最长真 border 的长度恰为 $L-p$；没有非空真 border 时，长度计为零。

全部 border 可以沿“当前字符串取最长真 border”组成的链列举。因为任意较短 border 都是最长真 border 的 border，反过来也成立，所以链上的每个正长度恰对应一个非空 border。

### 2. 长度至少为两倍周期的前缀

设 $w$ 的最短周期为 $p$。任取长度 $\ell\ge2p$ 的前缀，它当然具有周期 $p$。

假设它另有周期 $q<p$。对 $0\le i<p$，位置 $i$ 和 $i+q$ 都落在前 $2p$ 个字母中，因此

$$
w_i=w_{i+q}=w_{(i+q)\bmod p}.
$$

所以长度为 $p$ 的周期块在循环平移 $q$ 后保持不变。重复这个周期块得到的无限字符串具有周期 $q$，从而原字符串 $w$ 也具有周期 $q$，与最短周期的定义矛盾。

因此，这个前缀的最短周期仍为 $p$，最长真 border 的长度恰为 $\ell-p$。

### 3. 分阶段剥去 border

考虑 border 链上的当前字符串，长度为 $L$，最短周期为 $p$，记

$$
k=\left\lfloor\frac Lp\right\rfloor,\qquad
L=kp+t,\quad 0\le t<p.
$$

若 $k=1$，最长真 border 的长度为 $L-p<L/2$。这一阶段剥去当前完整字符串对应的一项，长度至少减半。若剩余长度为零，链直接结束。

若 $k\ge2$，由上一节可连续剥去 $k-1$ 项，它们的长度依次为

$$
L,L-p,\ldots,2p+t,
$$

留下的长度为

$$
L'=p+t<2p.
$$

这一阶段的成本为 $k-1$，长度缩小比例满足

$$
\frac L{L'}=\frac{kp+t}{p+t}\ge\frac{k+1}{2}.
$$

留下的字符串是原方向字符串的前缀，所以仍然对应一条没有重复顶点、能放进同一网格的路径。后续阶段可以继续使用全部条件。

### 4. 网格范围限制周期重复次数

设前 $p$ 步的净位移为 $d$。路径没有重复顶点，所以 $d\ne0$。周期性使第

$$
0,p,2p,\ldots,kp
$$

步的顶点坐标形成等差序列

$$
x_0,x_0+d,x_0+2d,\ldots,x_0+kd.
$$

非零整数向量 $d$ 至少有一个坐标的绝对值不小于 $1$。这些顶点都在 $n\times n$ 格点方框内，因此

$$
k\le n-1.
$$

### 5. 对阶段成本求和

先考虑 $n\ge4$，令

$$
C_n=\frac{n-2}{\ln(n/2)}.
$$

函数 $r/\ln(1+r/2)$ 在 $r>0$ 上单调递增。因此，对 $k\ge2$ 的阶段，令 $r=k-1\le n-2$，有

$$
k-1\le C_n\ln\frac{k+1}{2}
\le C_n\ln\frac L{L'}.
$$

对于 $k=1$ 且剩余长度非零的阶段，成本为 $1$，长度至少减半。由于 $C_n\ge1/\ln2$，这一阶段也满足相同的成本上界。

最后一次从正长度变成零的步骤单独计 $1$。其余阶段的对数相加后得到

$$
B(w)\le C_n\ln L+1.
$$

没有重复顶点的路径至多使用 $n^2$ 个格，因此 $L<n^2$。再用 $n\ge4$ 时的 $\ln n\le2\ln(n/2)$，有

$$
B(w)\le\frac{2(n-2)\ln n}{\ln(n/2)}+1
\le4n-7<4n.
$$

对于 $n\le3$，直接使用 $B(w)\le L\le n^2-1\le4n$ 即可。空字符串的 border 数量为零。引理得证。

## 道路是路径，查询从单端增长

先假设查询的全部新位移沿一条简单路径，从固定起点依次向前增加，方向字符串记为 $S$。

固定道路格 $v$，再固定抵达 $v$ 时使用的宿主边 $e$。收集所有以 $v$ 为终点、最后一步经过 $e$ 的成功检查，用 $j$ 表示查询沿这条路径增加了多少条边。

宿主分量是一条路径。从 $v$ 沿 $e$ 反向前进，后续路径唯一，因此这些成功检查对应的宿主路段按长度嵌套。

取这组成功时刻中最大的长度 $J$。方向字符串 $S[0:J]$ 对应一条能放进道路网格的简单路径。任意较短成功长度 $j$ 都满足

$$
S[0:j]=S[J-j:J].
$$

这里使用左闭右开的字符串区间。因此，每个成功长度都是 $S[0:J]$ 的一个 border。根据引理，这一组至多有 $4n$ 次成功。

道路路径在 $v$ 至多有两条边，所以单端增长时，每格的成功检查总数满足

$$
H(v)\le8n.
$$

## 两端交替增长与任意行走

只要仍有候选起点，全部已访问位移的诱导图就必须能平移到宿主路径中，所以它本身也是路径。把最初位移 $0$ 固定为根，这条路径至多分成从根出发的两条臂。

每条臂上的新格只能按从根向外的顺序被发现。记两条臂各自的方向字符串为 $S_1,S_2$。两臂如何交替延长，以及在旧格间走了多少步，都不会改变各臂上的前缀关系。

固定 $v$、固定一条查询臂，再固定抵达 $v$ 的宿主边。任何一次完整查询前缀的成功，都意味着“仅沿该臂从根走到本次新格”的较弱条件成功。忽略另一条臂只会增加可行起点，不会漏掉本来要计数的成功。

因此，该组成功仍可按上一节的方法映射到同一个臂方向字符串的 border。这里比较的是**从固定根出发的臂前缀**，所以另一端的增长不会破坏前后缀关系。

每个目标格最多分成两条查询臂、两条宿主入边，共四组。由此得到

$$
\boxed{H(v)\le16n.}
$$

若某一步使位移图产生分支、环或其他无法放进宿主路径的结构，这一轮没有成功检查，之后候选为空。这种步骤不增加成功检查总数。

## 总扫描量与证明边界

每个候选起点至多失败并被删除一次，所以失败检查总数不超过 $N$。成功检查按目标道路格计数，得到

$$
W\le N+\sum_{v\in F}H(v)\le(16n+1)N.
$$

加上初始化和读取输入的 $O(n^2+m)$，即得前述复杂度上界。

证明的关键是：在宿主路径中，从目标格沿固定入边反向延伸后不会分叉。一般道路树不满足这个条件；两条逆向路径可能在更远处分叉，从而不再按长度嵌套。因此，这个证明只适用于道路森林最大度数不超过二的情形。