# 纸老虎序列：分段回溯与有界缓存

Codex（GPT-6）提供区间回溯输出，并将出题人的共享后缀方法用于有界缓存。程序：[alternative.cpp](alternative.cpp)。这是与[共享后缀主解](solution.zh.md)并列的低空间方案。

## 缓存较短版本

设字符缓存上限为 $B$ ，至少容纳初始串。程序取 $B=65536$ ，选择最大的 $h$ ，使 $L_h\le B$ .用共享后缀法构造 $S_h$ ，它也包含所有更早的版本。不展开其余版本，只保留长度和增长参数。

## 回溯一个输出区间

定义 $\operatorname{Emit}(v,s,c)$ ，依次输出 $S_v$ 从下标 $s$ 开始的 $c$ 个字符。

- 若 $c=0$ ，立即返回。
- 若 $v\le h$ ，从缓存中相应后缀直接输出这段内容。
- 否则令 $D=L_v-L_{v-1}$ .旧后缀内的下标 $s\ge D$ 映射为上一版本的 $s-D$ .
- 新前缀内的下标映射为 $(p_v+s)\bmod L_{v-1}$ .先分离与前缀相交的部分；如果映射跨越旧串末尾，再拆为末尾和开头两段。最后处理原查询区间中属于旧后缀的部分。

前缀长度 $D\le L_{v-1}$ ，所以前缀部分最多绕过旧串末尾一次，每次最多产生三个有序子区间。只顺序输出，不拼接中间结果。

## 正确性与复杂度

缓存内容由共享后缀证明保证正确。每次分解严格按照“循环复制前缀，再接旧串”的定义划分区间，映射后的子区间依次覆盖要求的字符且没有遗漏或重复。版本号严格下降，因此对版本号归纳即可证明整个输出正确。

设 $Z$ 为总输出字符数。缓存构造不超过 $O(B+N)$ .在每个回溯深度，各个非空输出区间互不重叠，总长度不超过 $Z$ ；深度最多 $N+1$ .一个安全的总时间界为 $O(B+N+(N+1)Z)$ ，空间为 $O(B+N)$ ，不计标准输出缓冲。该上界不声称与主解具有同样的最坏时间保证。

缓存让递归在较大的连续片段处停止，避免逐字符回溯到初始串。字符区最多约 64 KiB，适合输出较少历史版本或需要减少字符存储的场景。时间与内存比较见[主解实测](solution.zh.md#实测结果)。