Z 算法（Z-Algorithm）是一种线性时间复杂度的字符串模式匹配算法，用于在文本串 T 中高效定位模式串 W 的所有出现位置。其核心思想基于预处理生成的 Z 数组，该数组记录了字符串各位置的最长公共前缀信息。
-
Z 数组定义
给定长度为n的字符串S，Z 数组Z[i]表示从位置i开始的最长子串长度，该子串同时是S的前缀。例如：字符串 S: a a b c a a b x a a a z Z数组值: X 1 0 0 3 1 0 0 2 2 1 0 -
Z-box（匹配区间）
算法维护一个动态区间[L, R]，表示当前已知的最大右边界R，使得子串S[L...R]是S的前缀。通过该区间优化计算过程，避免重复匹配。 -
模式匹配应用
将模式串W与文本串T拼接为W$T（$为分隔符），计算其 Z 数组。若某位置的Z[i] = |W|，则W在T中匹配成功。
- 初始化
设置L = R = 0，Z[0]无意义（通常设为n或忽略）。 - 遍历字符串
对每个位置i（从1开始）： • 情况 1（i > R）：暴力扩展比较S[0...]与S[i...]，更新L和R。 • 情况 2（i ≤ R）：利用已有 Z-box 信息： ◦ 若Z[i-L] < R-i+1，则Z[i] = Z[i-L]。 ◦ 否则，从R+1开始暴力扩展，更新L和R。
• 时间复杂度：O(|W| + |T|)。每个字符最多被比较两次（扩展和暴力匹配）。
• 空间复杂度：O(|W|)，仅需存储 Z 数组。
- 示例 1
字符串: a a a a a a Z数组: X 5 4 3 2 1 - 示例 2
字符串: a b a b a b a b Z数组: X 0 6 0 4 0 2 0 - Z-box 动态过程
| 算法 | 时间复杂度 | 空间复杂度 | 核心思想 |
|---|---|---|---|
| Z 算法 | O(n+m) | O(n) | Z 数组与动态区间优化 |
| KMP | O(n+m) | O(m) | 部分匹配表（前缀函数） |
| BM | O(n/m) | O(m) | 坏字符与好后缀规则 |
| 暴力法 | O(nm) | O(1) | 双重嵌套循环 |
- 模式匹配：高效定位文本中所有模式出现位置。
- 最长回文子串：结合 Manacher 算法优化。
- 重复子串检测：通过 Z 数组快速识别周期性模式。