算法与数据结构 / 字符串查找算法 · naive matching / KMP / Boyer-Moore / Rabin-Karp / Z function：与整串前缀的匹配长度 待审核 3 / 15
Z function · Z-box

Z function：与整串前缀的匹配长度

KMP 的 prefix function 记的是 pattern 内部「最长相等真前后缀」的长度，失配时靠它决定 pattern 指针退到哪。Z function 记的是另一件事：对每个下标 ii，z[i] 是 ss 从 ii 起的后缀与 ss 整串的最长公共前缀长度。两者携带同一份信息，换了一种编码方式。本页先求出这个数组，再落到「拼接 pattern、分隔符与 text，一次求 Z function 即完成匹配」这个用法，最后给出两种编码的互相转换。

1 · 定义与朴素求法

Z function：对长度为 nn 的串 ss，z[i] 等于 ss 从下标 ii 起的后缀与 ss 本身的最长公共前缀长度。i=0i = 0 处这个定义退化成 ss 与自己比，约定 z[0] = n。

以 ababaca 为例，zz 数组是 [7, 0, 3, 0, 1, 0, 1]。z[2] = 3 说明从下标 2 起的 abaca 与整串共享前缀 aba，第四个字符处分道扬镳；z[1] = 0 说明 babaca 与 ababaca 连首字符都不同。

按定义直接算，就是对每个 ii 从零开始逐字符比到失配为止，最坏 O(n2)O(n^2)：全同串 aaaa…a 上每个 ii 都要一路比到串尾。

注 · z[i] 与 prefix function 的 prefix[k] 都在数「一段与前缀相同的长度」，落脚点却相反：z[i] 从 ii 往右看，prefix[k] 从 kk 往左看。同一个下标上两者一般不相等，ababaca 的 z[2] = 3 与 prefix[2] = 1 就对不上——它们描述的根本不是同一段字符。§4 给出把一方翻译成另一方的算法。

2 · Z-box 与摊还线性

朴素求法的浪费与 naive matching 同源：每个 ii 都从零起比，前面确认过的相等关系一次也没用上。Z 算法只多维护一样东西：Z-box，即已算过的位置中右端最靠右的那个匹配区间。写成右开区间 [l,r)[l, r)，它满足 s[l..r−1]s[l..r-1] 恰是 ss 的一段前缀。

新的 ii 落在 box 内时，s[i..r−1]s[i..r-1] 是 s[i−l..r−l−1]s[i-l..r-l-1] 的逐字符复制，而后者的 Z 值 z[i - l] 早已算好。于是 z[i] 可以先取 min(r - i, z[i - l])，这一段不必再比。取 min 的两种情形要分开看：

  • z[i - l] 小于 box 余量 r−ir - i：镜像位置的匹配在 box 内部就断了，断在哪里 z[i] 就断在哪里，这个位置一次字符比较都不用做。
  • z[i - l] 不小于余量：box 右端之外的字符没有任何已知信息，只能从下标 rr 处接着逐字符比下去。

由此得到复杂度：每一次比较成功都把 rr 往右推一格，而 rr 单调不减且不超过 nn，成功的比较总共不超过 nn 次；每个 ii 至多贡献一次失败比较。两项相加不超过 2n2n，整个构造是 O(n)O(n)。

「记住最右边界、镜像位置先抄已算好的值」这套记账法与本页并不绑定，Manacher 一页把它原样搬到回文上：Z-box 换成最右回文，min 的两项换成边界余量与镜像半径，论证逐字对应。

图 2-1 · Z function 的构造过程。绿色区间是当前 Z-box，蓝框是本步比较的两个位置，底部读数给出累计比较次数与 2n 上界。可改输入串观察 box 何时挪动。

警示 · min 的两项都不能省。写成 z[i] = z[i - l] 时多数串上仍然正确，因为 z[i - l] 本来就常常小于余量。穷举二字母表上长度不超过 8 的全部串，最短的反例是 aaa：正确的 zz 是 [3, 2, 1]，漏掉 min 算成 [3, 2, 2]——i=2i = 2 时镜像位置的 z[1] = 2 伸出了 Z-box 的右端 r=3r = 3，而 box 之外的那一位实际是串尾，根本不存在。core/z-function.ts 保留了这个错误版本 zBuggyNoMin，z-function.test.ts 把 aaa 这个反例钉住。

3 · 拼接一次求 Z 完成匹配

把 pattern、一个分隔符、text 依次接成 pattern + sep + text，对它求一次 Z function。落在 text 区段上的下标 ii，若 z[i] 达到 pattern 长度 mm，就说明从 ii 起的 mm 个字符与整串的前 mm 个字符相同，也就是与 pattern 相同，text 内下标 i−m−1i - m - 1 处即有一次出现。一趟扫描给出全部出现位置，代价 O(n+m)O(n + m)，且不需要任何单独的预处理表。

图 3-1 · 拼接串上的一次 Z function 求解即完成匹配，橙色是 pattern 区段，黄色是分隔符，绿色是被判定命中的区间。分隔符可切到 c 观察与 text 撞车的后果。

警示 · 收口条件多写作 z[i] === m，它默默要求分隔符在 text 与 pattern 里都不出现。分隔符一旦与 text 撞车，z[i] 就可能越过 mm：取 pattern 为 ab、分隔符为 x、text 为 abx，拼成 abxabx，它的 zz 是 [6, 0, 0, 3, 0, 0]，唯一那处出现落在 i=3i = 3 上而 z[3] = 3，被 === m 判掉，一个匹配也报不出来。改成 z[i] >= m 与分隔符无关：这个不等式本身已经意味着那 mm 个字符逐位等于 pattern。本页实现取后者，前者留在 matchesStrict 字段里供对照。

4 · 两种编码的互换

同一个串的两个数组摆在一起，就能看出它们是同一份信息的两种写法：

下标 0 1 2 3 4 5 6
ababaca a b a b a c a
z[i] 7 0 3 0 1 0 1
prefix[i] 0 0 1 2 3 0 1

转换的依据是两条互为镜像的蕴含：

  • z[i] = k > 0 说明 s[i..i+k−1]s[i..i+k-1] 是前缀，对每个 0≤j<k0 \le j < k，位置 i+ji + j 处存在一个长 j+1j + 1 的 border，即 prefix[i + j] >= j + 1。
  • prefix[j] = k > 0 说明 s[j−k+1..j]s[j-k+1..j] 是前缀，即 z[j - k + 1] >= k。

由第一条得到 z 到 prefix 的直接写法：外层遍历 ii，内层让 jj 从 z[i] - 1 递减，逐格写下 prefix[i + j] = j + 1，一旦撞上已写过的格子就停——那格的 border 只会更长，后面的写入都是无用功。内层每写一格就永久占掉一个位置，所以总写入次数不超过 nn，整个转换是 O(n)O(n)。

图 4-1 · 由 z 数组译出 prefix function 的逐格写入。绿色是已写定的格子，红色是撞上已写格而中止的那一步，读数给出与直接计算的结果是否一致。

反方向要绕一些：先把每个 prefix[i] 反着记成 z[i - prefix[i] + 1] 的一个下界，再从这些下界出发向右摊开尚缺的值，实现见 zFromPrefix。两个方向都在三字母表上长度不超过 9 的全部串上验证过。

两种编码等价，不等于两条实现同样省。在同一组输入上数字符比较次数：abracadabra 里找 abra，KMP 的 prefix function 构建用 3 次、扫描用 13 次，合计 16 次，而拼接求 Z function 用了 23 次；aaaaaaaaaaab 里找 aaab，naive 36 次、KMP 25 次、Z function 29 次。差距来自两处：Z function 在长 n+m+1n + m + 1 的串上工作，且 z[0] 到 z[m] 这一段完全花在 pattern 内部。拼接法的价值是代码短、边界条件少，不在比较次数。

5 · 参考文献

  1. Gusfield, D. (1997). Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology. Cambridge University Press.
  2. Knuth, D. E., Morris, J. H., & Pratt, V. R. (1977). Fast pattern matching in strings. SIAM Journal on Computing, 6(2), 323–350.