Z 函数

把前缀移到每个位置，能对上多长 ​

给定字符串 $s$，把它的整个前缀与从位置 $i$ 开始的后缀对齐，从左到右比较，直到第一次失配或后缀结束。匹配的长度就是 $Z[i]$。Z 函数把这件事对所有位置同时做好，因而能快速回答“这个位置是否出现了开头那一段”。

Z-box：让已有匹配替下一次比较作证 ​

从左到右处理位置，维护一个已经算出的匹配区间 $[l,r)$，满足

并使右端点 $r$ 在已处理位置形成的区间中最靠右。这个区间称为 Z-box。

若 $i\ge r$，当前没有覆盖 $i$ 的可用匹配信息，就从长度 $0$ 开始比较。若 $i<r$，位置 $i$ 在 box 内对应前缀中的位置 $k=i-l$，因此至少可以复制

这一段已知相等的信息。这里必须取最小值：$Z[k]$ 可能延伸到旧 box 覆盖不到的地方，那部分尚未被证实。

接下来分两种情况理解。若 $Z[k]<r-i$，导致 $Z[k]$ 停止的失配也落在 box 内，便有 $Z[i]=Z[k]$，答案已经确定。若 $Z[k]\ge r-i$，目前只能确认一直匹配到 $r$，需要从边界继续向右试。得到完整答案后，若 $i+Z[i]>r$，就令 $l=i$、$r=i+Z[i]$。

在上例中，位置 $4$ 建立 $[4,7)$。处理 $i=5$ 时，复制 $Z[1]=1$，而 $1<7-5$，所以已有失配足以确定 $Z[5]=1$。处理 $i=9$ 时，旧 box 是 $[8,10)$，只能先复制到边界的一位；再比较发现下一位也相同，才能把答案延长为 $2$。

最小实现与线性时间证明 ​

下面把两种情况合并到同一段代码中；已知 box 内会失配时，while 的第一次比较会立即停止。

def z_function(s: str) -> list[int]:
    """返回 Z 数组，采用 Z[0] = 0 和半开区间 [left, right)。"""
    n = len(s)
    z = [0] * n
    left = right = 0
    for i in range(1, n):
        if i < right:
            z[i] = min(right - i, z[i - left])
        while i + z[i] < n and s[z[i]] == s[i + z[i]]:
            z[i] += 1
        if i + z[i] > right:
            left, right = i, i + z[i]
    return z

assert z_function('aabcaabxaaaz') == [0, 1, 0, 0, 3, 1, 0, 0, 2, 2, 1, 0]

正确性的关键是 box 内的字符串与前缀完全相同，因此复制给出的下界可靠，box 内的失配也可靠；边界外的新比较则把答案补到首次失配。每次更新 $[l,r)$ 都由一次实际匹配支持，不变量随之保持。

复杂度不能用“每次比较都推进右端点”来证明，因为失配比较并不推进任何东西。准确的记账是：成功的新比较只发生在旧右边界及其右侧，每成功一次就把当前已探索的边界推进一位，全部迭代合计至多 $n-1$ 次；每个外层位置至多再产生一次失配比较。于是字符比较总数为 $O(n)$，时间为 $O(n)$，结果数组占 $O(n)$ 空间。[1]

Manacher 算法理路Manacher 回文半径算法Manacher's algorithm · 马拉车算法在最右回文内镜像复用已知半径，只对越过右边界的部分重新比较，在线性时间计算所有奇偶中心的最大回文半径。在回文问题中采用相近的边界复用记账，但复用的是中心镜像半径，既不是前缀匹配长度，也不能直接套用本页的镜像下标。其奇、偶中心各自维护已证实回文，成功扩张与每中心至多一次的失配分别收费。

匹配、border 和周期 ​

对非空模式 $P$ 与文本 $T$，构造 P#T，其中 # 不出现在二者中。令 $m=|P|$；拼接串中位置 $i\ge m+1$ 满足 $Z[i]\ge m$，当且仅当文本位置 $i-m-1$ 开始出现一次完整的 $P$。因为分隔符阻断继续匹配，这些位置实际上有 $Z[i]=m$。例如 aba#ababa 会报告文本中的位置 $0$ 和 $2$，重叠出现也不会漏掉。若字符表没有可用分隔符，可先把字符编码为整数，再使用一个表外标记。

长度 $b$ 是整个字符串的非空真 border，当且仅当 $1\le b<n$ 且 $Z[n-b]=b$。这里 border 指既是前缀又是后缀的同一段内容。类似地，$1\le p<n$ 是一个周期，当且仅当 $Z[p]=n-p$：这恰好检查了所有 $s[j]=s[j+p]$。周期长度不必整除 $n$；要判断字符串是否由同一块整数次重复组成，还需 $p\mid n$。

周期与 border理路字符串的周期与 borderPeriod of a word · Border of a word · 字符串周期 · 前后缀重合用错位后仍相等的位置定义有限字符串的周期，并把长度 p 的周期与长度 n-p 的前后缀重合一一对应。将本段两个判据连成位移与重合长度的完整对应。利用 Z 数组核实两个周期后，仍不能无条件取它们的最大公约数：Fine–Wilf 引理理路Fine–Wilf 周期引理Fine–Wilf theorem · Periodicity lemma · Fine-Wilf周期定理长度至少为 p+q−gcd(p,q) 的有限词若同时具有周期 p、q，就必有周期 gcd(p,q)。给出所需长度，长度六的 abaaba 则说明周期三、五并不自动带来周期一。

前缀函数理路前缀函数Prefix function · Failure function记录每个前缀的最长真前缀—后缀重合长度的字符串函数。 $\pi [i]$ 以“当前位置结尾的前缀”为对象，Z 函数以“当前位置开头的后缀”为对象。两者的数组一般不相等，但在有效数组之间可以在线性时间互相转换；这里的“等价”指前缀重合信息可相互恢复，不表示逐项相等，也不允许混用下标公式。