这项任务把“在哪里找到匹配”和“选哪几个匹配”分开核验，再把两者接成真正能解回原文的位流。交付物不只是压缩比，而是一份可以定位错误的账本：哪个来源仍在窗口内、为什么只查两个邻居、为什么某个短匹配更省、每个位在哪里、恶意长度在哪一步被拒绝。

入口是滑动历史最长匹配理路滑动历史窗口的最长匹配Sliding-window longest match · Historical distance-band matching · 历史距离带匹配在完整字节串的后缀索引上维护到期删除的历史秩集合，用两个活动字典序邻居求每个位置的距离带最长匹配及来源见证。与固定位费用最优解析理路固定位费用的LZ77最优解析Fixed-cost LZ77 parsing · Gamma-cost LZ77 parsing · 固定位码制的最优回指解析固定字面量与gamma长度距离码的逐token位费用，以距离价格带和长度价格区间压缩完整转移，求可重建且可解码的最小payload。。返回完整路线。

固定输入、接口与复现 ​

所有位置和后缀秩从0开始，数组范围用半开区间。输入是不可变 bytes，没有字符编码或Unicode归一化步骤。LZ匹配最小长度3，允许长度大于距离的重叠复制。窗口和最大长度可为0；布尔值不作为整数接受。

• 完整Python参考器，只用标准库，直接执行向标准输出写JSON
• 同版实际完整结果，含所有示例轨迹、DP选择和下列八份恶意bit见证

python3 algorithms-window-lz77-check.py > result.json
python3 -O algorithms-window-lz77-check.py > result-optimized.json
cmp result.json result-optimized.json

参考器内用显式条件抛异常，关闭Python断言不应改变结果。它包含作者交叉检查；独立审查的收据不由这些自测替代。

接收payload还必须知道原文长度 size、有效位数 valid_bits、window 与 cap；它不是DEFLATE，也不是自描述文件格式。

任务一：建立可检查的后缀索引 ​

对 ABAABABA 交出SA、逆秩和相邻前驱LCP，不能只给排序后的字符串。应得到

SA   = [7,2,5,0,3,6,1,4]
rank = [3,6,1,4,7,2,5,0]
LCP  = [0,1,1,3,3,0,2,2]

手算位置5与位置0：它们秩为2、3，查询 LCP[3:4]，答案3。位置5与位置3的秩为2、4，查询 LCP[3:5]，最小值仍为3。同一起点相较直接返回剩余后缀长度，不向树查询空区间。

实现必须运行计数排序倍增和Kasai，不得把 sorted(key=lambda p:T[p:])当成所宣称的主算法。后者只出现在小规模校验器中。说明虚拟终止符如何与原始零字节区分，并用 bytes(range(256))和重复零/255的输入核验。若把字节0直接当唯一哨兵，这两类测试会暴露假设。

交付： 三个数组、两次RMQ端点、哨兵映射和实际小规模逐后缀比较结果。预处理按 $O((n+1)\log (n+2))$ 计费，不把带切片的校验排序混入该界。

任务二：走过窗口，而不是只查一次 ​

运行 SuffixIndex(b'ABAABABA').band(1,5,8,True)，交出全部八个位置的插入、到期、活动来源秩序和两个候选。重点检查 $p=5$：

当前秩2
活动来源按秩：[2,0,3,1,4]
前驱来源2、秩1、长度1
后继来源0、秩3、长度3
答案：(3,0)，距离5

再运行 band(2,3,8,True)。在 $p=4$ 后推进一步，插入来源3、删除来源1；$p=5$ 的活动来源按秩为 [2,3]，答案是 (3,3)、距离2。解释每位置先插入 p-a、删除 p-b-1 后，集合为何恰等于允许历史。用任意一侧更远活动秩的LCP区间包含关系，证明两候选足够。

接着制造四种边界：空串、上限0、下界超过全部已有前缀、$a=b$ 的单一距离。正长度见证必须属于当前集合且实际匹配该长度；零长度统一配 None，不能仅用“集合为空”来判断零答案。

交付： 两份实际轨迹和不变量证明。指出宽带见证的距离5不是最小距离，并说明为什么贪心跳过若干输入位置后仍必须把它们正确加入历史。完整活动集合日志最坏占平方空间，不能和核心扫描混报。

任务三：把价格档变成完整转移 ​

手写本任务的码价：字面量 0 加8位字节收9bit；匹配收 1 + gamma(ℓ-2) + gamma(d)。gamma用前导零加完整二进制表示。列出1到8的整数码并检查解码边界。

对距离档 [1,1]、[2,3]、[4,7] 分别说明码长为什么恒定。针对任务二的 $p=5$，验证 Match(3,5)为7bit、Match(3,2)为5bit。必须分别求档内最长见证，不能只把宽带答案带入费用式。

证明：在一个固定距离档中，可用长度恰是 $3$ 到该档最长值 $M$。如果任意较短长度可行，它不会超过 $M$；如果 $\ell \le M$，最长见证的前 $\ell$ 字节就是有效来源。由此给出长度档 [3,3]、[4,5]、[6,9]，与 [3,M]相交，再把闭长度区间 [L,U]转换为目的位置半开区间 [p+L,p+U+1)。

交付： 码表、档内完备性证明、区间端点和一次实际 (费用,目的位置)的区间查询。说明为什么最小匹配长度3使“把任意匹配截短一两个字节”不再自动合法，不能凭空套用最长边剪枝。

任务四：复算七个A，并恢复所有选择 ​

运行 optimal_parse(b'AAAAAAA',8,18,True)，得到完整表

p    0  1  2  3  4   5  6  7
D   15  6  5  5  3  18  9  0

把 $D[p]$ 定义成从相同原文前缀状态出发的剩余最小费用，说明此前token划分为什么不影响后续合法匹配。按所有边都向右证明求值顺序，再逐格给出字面量候选与获胜选择。费用非单调：$p=5$ 剩两字节，必须发两个字面量，因此18比 $D[4]=3$ 大。

在 $p=1$ 的距离1档，长度3候选为6，长度4到5候选为14，长度6候选为7。真正选的是长度3。沿选择恢复

Lit(A), Match(3,1), Match(3,1)
路径 0 → 1 → 4 → 7，费用9+3+3=15

贪心则为 Lit(A), Match(6,1)，费用16。交出二者的逐token费用；通过沿路径累加 $D[p]=c+D[p^{\prime }]$ 证明恢复方案恰达到 $D[0]$，而不是只验证它可以解码。

再对 $W=0$ 或 $C=2$ 重跑，核实全字面量费用63。空输入返回0。最后解释：若改成依赖整块频数的码表，为什么当前一维状态和位价不再自动证明最优。

任务五：真正打包与解码 ​

分别调用 encode_tokens和 decode_payload，比较输出字节与原文。七个A的精确结果是

贪心有效位：0010000011001001  （16位）  payload=20c9
最优有效位：001000001111111   （15位）  payload=20fe

第二个payload末尾有一位零填充，不能把它算作新的有效token。两者都是两字节，交付时要同时写有效位和物理字节，不得把“一位更省”说成“文件少一字节”。

对 ABABABABA、$W=2,C=7$，应解析成 Lit(A),Lit(B),Match(7,2)。给出复制源/目标表：

第三步开始就读本token刚写出的内容。必须按从左到右的生成顺序执行，不能预先截取不够长的原历史片段。另造五个字面量 A,B,A,A,B 后接 Match(3,1)，设总长度8、窗口5、上限8。它通过语法与边界检查，却恢复 ABAABBBB，不是任务一的 ABAABABA。编码器不知道未提供的原文；最终原文一致性要由匹配算法和解码比较建立。

交付： 有效位串、十六进制、外部参数、实际恢复字节和完整复制轨迹。核算位串处理 $O(B+n+1)$，不要只报回指token个数。

任务六：让拒绝路径与成本同样可复现 ​

下面每行是直接拼出的恶意payload，不经过会先校验token的编码函数。有效位数明确限制读取范围，剩余物理位均为零填充。将十六进制转为 bytes，按给出的 valid_bits,size,window,cap调用解码器，核对拒绝原因。

第一行在字面量A后读到匹配标志1及一个零，却没有整数其余位。第2行试图编码长度5，而cap只有4；第5行使用同样的bit却声明总输出5，字面量之后只剩4格，所以也必须拒绝。第3行已输出AB，仍试图用距离3越过窗口2。第4行的距离根本没有正整数合法域。第6行已经完成声明的一字节，还留一个有效0，不能当作允许忽略的padding。第7行缺距离码后续位；第8行在等待整条码字到齐前就已超允许位长。

另外复现负预算、输出预算不足、位预算不足、物理payload多一个字节、末尾非零填充和截断字面量。不能以“最后解出来不对”代替明确的拒绝；尤其要确认长度/距离检查发生在复制循环之前。默认预算只是参考值，任何调用都必须有明确资源合同。

公开程序的实际自测应报告：511个二元串（长度0到8的全枚举）、80个随机串、145094个历史带位置、9456组最优解析配置、23个拒绝见证；普通模式与 -O 的完整JSON字节相同。SA和LCP逐项对照字节比较，历史带对照枚举真实来源，位价对照枚举每个距离与每个合法长度的前向最短路。新增的八份坏bit证书保存在 refusal_witnesses 字段；请同时保留实际输出，不只抄这里的总数。

最后交成本账单。设非空距离价格档数为K、可能长度价格档数为J：核心时间为 $O((n+1)\log (n+2)+nK(J+1)\log (n+2))$，存储为 $O(n(K+1)+1)$；距离带完整活动轨迹和DP候选轨迹分别另计。列出这几个容易漏算的对象：完整后缀索引、全部K档匹配表、DP恢复选择、位串与返回输出、大整数、暴力oracle和JSON。报告自己改动后的复杂度时，以实际保留的数据和调用次数为准。

最终交付： 可执行器与参数、六项任务的计算过程和输出、一个错误算法的具体反例、八个恶意bit见证与预算拒绝、复杂度解释。最长匹配正确、解析最优、位流唯一可解、资源限制有效，是四项分别需要证据的结论。