滑动历史窗口的最长匹配

解码器已经知道“往回两格、复制七字节”，可以逐字节照做。编码器却得先找到这两个数。逐个距离反复比较会把同一段文字读很多遍。本页把历史位置放到另一种顺序中：按它们开始的后缀排序，再问当前后缀左右最近的两个合法邻居。关键是“合法”也会随窗口移动，不能拿整张后缀数组里的相邻项直接替代。

形式陈述

输出长度，还要输出一个可用来源

输入为完整不可变字节串 $T[0..n)$ ，以及整数 $1\le a\le b$ 、长度上限 $C\ge0$ 。在位置 $p$ ，允许的历史起点集合为

H_p(a,b)=\{q:0\le q<p,\ a\le p-q\le b\}.

SuffixIndex(T).band(a,b,C) 为每个 $0\le p<n$ 返回 $(M_p,q_p)$ ，其中

M_p=\max\bigl(\{0\}\cup \{\min(C,n-p,\operatorname{lcp}(T[p..n),T[q..n))):q\in H_p(a,b)\}\bigr).

若 $M_p>0$ ，见证 $q_p\in H_p(a,b)$ 必须达到该长度；若 $M_p=0$ ，本接口统一返回 None，即使历史集合并不空。它不承诺找最近来源，也不承诺枚举全部并列来源。普通窗口 $W\ge1$ 就是 $(a,b)=(1,W)$ ； $W=0$ 的解析器另行把所有位置视为没有回指。

这里沿用LZ77重叠回指：来源只要求开始于过去，不要求整段结束于 $p$ 之前。若 $q=p-d$ ，合法匹配满足 $T[p+i]=T[p+i-d]$ ；当 $i\ge d$ 时，解码器读到的是本token此前刚写出的字节。因 $d\ge1$ ，逐字节复制始终先有源再有目标。不能再把长度截为 $d$ ，那会变成另一个不允许重叠的问题。

本页建立完整输入的离线索引。利用未来字节来比较后缀是编码端的工作，不意味着解码器能读取未来。接口也不是只保留 $W$ 字节的在线编码器。

两个活动邻居足够

设 $r=ISA[p]$ 。把合法来源的后缀秩组成集合 $A_p=\{ISA[q]:q\in H_p(a,b)\}$ 。从中取小于 $r$ 的最大秩 $u$ ，以及大于 $r$ 的最小秩 $v$ ；不存在的一侧略去。最长匹配一定可以由 $SA[u]$ 或 $SA[v]$ 达到。

证明直接使用LCP数组的区间最小值等式。若活动秩 $s<u<r$ ，则

\min_{s<t\le r}LCP[t]\le\min_{u<t\le r}LCP[t].

左侧更远的来源不可能比最近活动前驱更长。右侧同理：从当前秩到更远来源的区间包含到最近活动后继的区间，最小值只会不增。再统一截到 $C$ 和 $n-p$ ，大小关系仍保持。注意，中间可以夹着很多不活动后缀；定理要求最近活动邻居，不要求秩差为一。[1]

插入、到期与顺序统计

按 $p=0,1,\ldots,n-1$ 扫描，每次先插入 $q=p-a$ ，再删除 $q=p-b-1$ ，忽略负起点。查询前维持不变量

A_p=\{ISA[q]:\max(0,p-b)\le q\le p-a\}.

当右端小于左端时集合为空。初始没有历史；从 $p-1$ 到 $p$ ，右端恰好新增 $p-a$ ，左端恰好越过 $p-b-1$ ，所以归纳得到上述集合。每个合法秩的频率始终为0或1，当前秩从不活动。

用Fenwick树维护这些0/1频率。prefix(r)统计小于当前秩的活动项数，记为 $s$ ；prefix(n)为总数 $z$ 。若 $s>0$ ，第 $s$ 个活动秩就是前驱；若 $s<z$ ，第 $s+1$ 个就是后继。第 $k$ 个1通过树上二进制提升求出：从大块到小块试探，若候选前缀计数仍小于 $k$ ，就跨过它并减去这块计数。非负频率保证前缀单调。

text

for p = 0 .. n-1:
    insert rank[p-a] if p-a >= 0
    erase  rank[p-b-1] if p-b-1 >= 0
    s = active.prefix(rank[p]); z = active.prefix(n)
    neighbors = kth(s) if s>0, then kth(s+1) if s<z
    best = 0; witness = None
    for r in neighbors:
        q = SA[r]
        length = min(C, n-p, LCP_query(p,q))
        if length > best: best = length; witness = q
    output (best,witness)

严格大于才更新，故两侧正长度并列时保留前驱。这是确定性规则，不是“选最小距离”的规则。

直觉

把全部后缀想成按字典序排好的书。当前后缀和某本书共享很长开头，就意味着夹在它们之间的每本书也共享这个开头。于是同一侧最靠近当前后缀的合法书不会更差。

窗口负责决定哪些书有资格，LCP负责比较内容。一个位置从时间上过期，只把对应秩的计数减一；书架和相邻LCP不需要重排。反过来，只在输入位置上保留最近两个来源是不够的，因为时间邻居与字典序邻居是两种顺序。

ABAABABA在位置5的活动后缀；全历史邻居见证距离5，而距离带2到3保留同长度的更便宜来源 — 历史位置与活动后缀秩

例子与边界

同长度，不同距离费用

取 ABAABABA，位置从0开始， $p=5$ 的后缀是 ABA。后缀数组及LCP为

SA=(7,2,5,0,3,6,1,4),\qquad LCP=(0,1,1,3,3,0,2,2).

在距离带 $[1,5]$ 中，历史来源按后缀秩排列为 $(2,0,3,1,4)$ ；当前位置的秩为2。最近活动前驱为 $q=2$ ，共享 A、长度1；后继为 $q=0$ ，共享 ABA、长度3。因此返回 $(3,0)$ ，距离为5。

然而 $q=3$ 也以 ABA 开头，长度同为3，距离只有2。它被 $q=0$ 挡在更远的字典序位置，两个邻居规则没有义务报告它。在固定费用解析的码制里，Match(3,5)花7bit，Match(3,2)只花5bit。最长长度正确，不等于复制来源已经最便宜。

把来源改限于距离带 $[2,3]$ ， $p=5$ 时只有 $q=2,3$ 活动；两个邻居现在给出 $(3,3)$ 。从 $p=4$ 推进过来时插入 $q=3$ ，删除刚到期的 $q=1$ ，不应保留距离4的旧来源。这也说明为什么下一页分别运行若干距离带，而不把一个任意最长见证当成全部价格档的答案。

重叠不是越界

对 ABABABABA、 $W=2,C=7$ ，在 $p=2$ 发现来源 $q=0$ 、长度7。源后缀与目标后缀都有足够字符；解码为 Lit(A), Lit(B), Match(7,2) 时，每次复制从当前输出末尾往回两格读取。第3个复制字节已经读到本匹配第1步写出的A。若错误加上“长度不得超过距离”，这个合法长匹配就会消失。

零、字节与表示边界

空串输出空列表。 $C=0$ 时每个位置的答案都是 $(0,\mathrm{None})$ 。最小距离大于已有前缀时，活动集合为空；最大距离超过 $n$ 也合法，只是从未产生那么远的来源。长度1或2仍是匹配接口的有效答案，教学LZ解析器随后因最小token长度3而不用它们。

输入可含全部256种字节，包括零字节与255。构造时把每个字节 $x$ 映成 $x+1$ ，再添加唯一虚拟终止符0；不能把原输入中可能出现的零字节当唯一哨兵。完整公开代码拒绝负上限、倒置距离带、布尔值冒充整数及非不可变字节输入。

推论与应用

预处理与实际费用

公开实现采用后缀数组的计数排序倍增构造：在带唯一终止符的循环串上按长度1、2、4……的秩对排序，每轮用已排序的后半部顺序和前半部计数排序完成线性工作，最后删除终止符后缀。随后用Kasai扫描构造前驱LCP。输入字母表固定为字节，预处理时间为 $O((n+1)\log(n+2))$ 。

LCP数组静态存入线段树，两后缀的公共前缀通过相应区间最小值求得。它在本实现中每次花 $O(\log(n+2))$ ，不是常数查询。Fenwick的单点增减、前缀和与第 $k$ 个1也各花对数时间。每位置至多两次LCP查询，因此一个距离带的完整扫描为 $O((n+1)\log(n+2))$ ；含预处理仍同阶。SA、逆秩、LCP、两棵树和全部输出共 $O(n+1)$ 个字。

trace=True另列出每个位置的完整活动集合，并逐项调用顺序统计。最坏额外时间为 $O(n^2\log(n+2))$ 、日志空间为 $O(n^2)$ 。这是演示账本，不属于不带轨迹的线性空间接口。所有界按索引、计数、输入字节和长度装入机器字计费；更大整数另算位成本。

若只要一个贪心解析，先求所有位置的答案，再按token跳过已消费位置。不能在跳跃时只做一次插入删除，否则活动集合会遗漏被跳过的历史。公开 greedy_parse正是先完整扫描，后读取解析起点。

文献中的KKP算法在完整历史模型上进一步利用特定PSV/NSV结构达到线性界；本页的到期距离带、Fenwick和树查询不是那段实现，不继承它的线性结论。[1] 更重要的后续是把距离费用分组：同一价格档只需一个最长见证，便能支持该档所有更短合法匹配；跨价格档仍须保留区别。

完整终点任务要求交出实际活动秩、到期动作、匹配见证和逐字节复制结果，再把这些证书用于位费用优化。

参考资料

[1] Juha Kärkkäinen, Dominik Kempa and Simon J. Puglisi, Linear Time Lempel-Ziv Factorization: Simple, Fast, Small, CPM 2013, pp. 189–200，§2 的LPF与两个字典序候选，§§3–5 的线性实现。本文把候选证明用于指定活动子集，窗口更新和成本另外证明；不是照搬无到期历史的线性算法。
Paolo Ferragina, Igor Nitto and Rossano Venturini, On the Bit-Complexity of Lempel-Ziv Compression, SIAM Journal on Computing 42(4), 2013, pp. 1521–1541，§§3、5.2：复制距离费用和历史窗口分组。
L. Peter Deutsch, RFC1951, §3.2.3：重叠长度/距离复制的具体语义；本文没有生成DEFLATE块。

形式陈述 ​

输出长度，还要输出一个可用来源 ​

两个活动邻居足够 ​

插入、到期与顺序统计 ​

同长度，不同距离费用 ​

重叠不是越界 ​

零、字节与表示边界 ​

预处理与实际费用 ​

反向链接