Z 算法(Z-Algorithm)

Z 算法(Z-Algorithm)是一种用于字符串处理的线性时间算法,其核心是计算字符串的 Z 数组:对长度为 n 的字符串 s,Z 数组的第 i 项 z[i] 表示从位置 i 开始的子串与 s 本身的最长公共前缀的长度。利用 Z 数组,可以高效地解决字符串匹配等一系列问题。

概述

许多字符串问题都可归结为求某个后缀与整串前缀匹配多长。Z 算法通过维护一个已知匹配区间来避免重复比较,从而在 O(n) 时间内一次性算出所有位置的 Z 值。它与 KMP 算法功能相近,但思路更直观,代码也更简洁。

核心原理

算法维护一个当前已知的、与前缀匹配的最靠右区间,通常记为 [l, r],称为 Z-box。处理位置 i 时:若 i 落在该区间内,则可以利用之前已算出的 z 值直接跳过一部分比较;若超出区间或跳过后仍需扩展,则从当前位置逐字符向后匹配,并相应更新区间 [l, r]。

• 区间复用:落在 Z-box 内的位置借助对称性直接推断部分 z 值,减少重复比较。
• 线性复杂度:右边界 r 只增不减,总的字符比较次数是线性的。
• 模式匹配:把模式串、分隔符和文本串拼成一个新串求 Z 数组,z 值等于模式长度的位置即为一次匹配。

应用场景

Z 算法可用于精确字符串匹配、寻找字符串的所有周期、求最长回文相关问题的辅助、以及许多竞赛中的字符串题。它与 KMP、Manacher 等同属线性字符串算法家族,常作为处理前缀匹配问题的通用工具。

常见问题

问:Z 算法和 KMP 有什么区别?答:两者都是线性时间字符串匹配算法。KMP 计算的是前缀函数(边界数组),Z 算法计算的是各位置与整串前缀的匹配长度;Z 算法通常被认为更直观易懂。

问:如何用 Z 算法做模式匹配?答:把模式串 P、一个不出现于两串的分隔符和文本串 T 依次拼接,对结果求 Z 数组,凡是 z 值等于模式串长度的位置,就对应文本中的一次成功匹配。