一类四邻接网格图森林的匹配问题：路径分量的三次方上界¶
历史研究记录（2026-10-12 更新）。 一般三次方上界现已由独立证明解决。下文保留各阶段的推导、余项和反例；“尚未解决”指当时状态或该局部方法，更强的辅助命题不自动随一般上界成立。
本文分析候选列表程序，给出道路森林的每个分量都是路径时的自包含证明。证明由 Codex（GPT-6）整理。一般森林的分析见主复杂度证明。
后续的根叶路径证明已把本子类的检查量改进为 \(W\le(6n-5)N\)，并覆盖道路可以分叉的路径查询。本文保留原有的方向字符串 border 证明及其独立引理。
结论与适用范围¶
设道路集合为 \(F\)，道路格数为 \(N\le n^2\)。如果道路森林的最大度数不超过 \(2\)，即每个分量都是路径或孤立点，则对任意输入行走序列都有
其中 \(W\) 为候选检查总数。
查询可以在已访问路径的两端交替延长，也可以在旧位移之间反复行走。若某次新增位移形成分支，就没有候选能够成功通过这一轮，因为道路路径不能容纳分支。
主复杂度证明中的独立水平条纹构造也属于这个子类。因此，当 \(m\ge n-1\) 时，这个子类的最坏情况上下界已经合拢为 \(\Theta(n^3+m)\)。
方向字符串的 border 数量引理¶
把不重复经过顶点的网格路径编码为方向字符串 \(w\)，长度 \(L\) 等于边数。一个非空字符串若同时是 \(w\) 的前缀和后缀，就称为它的一个 border（相等前后缀）。这里把整个 \(w\) 也计入 border，记数量为 \(B(w)\)。
引理。 如果这条路径可以平移放入 \(n\times n\) 网格，那么
这个引理只要求路径没有重复顶点，不要求它是诱导路径。以下给出不依赖外部字符串定理的证明。
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\) 个字母中，因此
所以长度为 \(p\) 的周期块在循环平移 \(q\) 后保持不变。重复这个周期块得到的无限字符串具有周期 \(q\)，从而原字符串 \(w\) 也具有周期 \(q\)，与最短周期的定义矛盾。
因此，这个前缀的最短周期仍为 \(p\)，最长真 border 的长度恰为 \(\ell-p\)。
3. 分阶段剥去 border¶
考虑 border 链上的当前字符串，长度为 \(L\)，最短周期为 \(p\)，记
若 \(k=1\)，最长真 border 的长度为 \(L-p<L/2\)。这一阶段剥去当前完整字符串对应的一项，长度至少减半。若剩余长度为零，链直接结束。
若 \(k\ge2\)，由上一节可连续剥去 \(k-1\) 项，它们的长度依次为
留下的长度为
这一阶段的成本为 \(k-1\)，长度缩小比例满足
留下的字符串是原方向字符串的前缀，所以仍然对应一条没有重复顶点、能放进同一网格的路径。后续阶段可以继续使用全部条件。
4. 网格范围限制周期重复次数¶
设前 \(p\) 步的净位移为 \(d\)。路径没有重复顶点，所以 \(d\ne0\)。周期性使第
步的顶点坐标形成等差序列
非零整数向量 \(d\) 至少有一个坐标的绝对值不小于 \(1\)。这些顶点都在 \(n\times n\) 格点方框内，因此
5. 对阶段成本求和¶
先考虑 \(n\ge4\)，令
函数 \(r/\ln(1+r/2)\) 在 \(r>0\) 上单调递增。因此，对 \(k\ge2\) 的阶段，令 \(r=k-1\le n-2\)，有
对于 \(k=1\) 且剩余长度非零的阶段，成本为 \(1\)，长度至少减半。由于 \(C_n\ge1/\ln2\)，这一阶段也满足相同的成本上界。
最后一次从正长度变成零的步骤单独计 \(1\)。其余阶段的对数相加后得到
没有重复顶点的路径至多使用 \(n^2\) 个格，因此 \(L<n^2\)。再用 \(n\ge4\) 时的 \(\ln n\le2\ln(n/2)\)，有
对于 \(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]\) 的一个 border。根据引理，这一组至多有 \(4n\) 次成功。
道路路径在 \(v\) 至多有两条边，所以单端增长时，每格的成功检查总数满足
两端交替增长与任意行走¶
只要仍有候选起点，全部已访问位移的诱导图就必须能平移到宿主路径中，所以它本身也是路径。把最初位移 \(0\) 固定为根，这条路径至多分成从根出发的两条臂。
每条臂上的新格只能按从根向外的顺序被发现。记两条臂各自的方向字符串为 \(S_1,S_2\)。两臂如何交替延长，以及在旧格间走了多少步，都不会改变各臂上的前缀关系。
固定 \(v\)、固定一条查询臂，再固定抵达 \(v\) 的宿主边。任何一次完整查询前缀的成功，都意味着“仅沿该臂从根走到本次新格”的较弱条件成功。忽略另一条臂只会增加可行起点，不会漏掉本来要计数的成功。
因此，该组成功仍可按上一节的方法映射到同一个臂方向字符串的 border。这里比较的是从固定根出发的臂前缀，所以另一端的增长不会破坏前后缀关系。
每个目标格最多分成两条查询臂、两条宿主入边，共四组。由此得到
若某一步使位移图产生分支、环或其他无法放进宿主路径的结构，这一轮没有成功检查，之后候选为空。这种步骤不增加成功检查总数。
总扫描量与证明边界¶
每个候选起点至多失败并被删除一次，所以失败检查总数不超过 \(N\)。成功检查按目标道路格计数，得到
加上初始化和读取输入的 \(O(n^2+m)\)，即得前述复杂度上界。
证明的关键是：在宿主路径中，从目标格沿固定入边反向延伸后不会分叉。一般道路树不满足这个条件；两条逆向路径可能在更远处分叉，从而不再按长度嵌套。因此，这个证明只适用于道路森林最大度数不超过二的情形。