算法背景
Z函数（Z-Function / Z-Algorithm）是字符串处理中的经典算法，用于在 $O(n)$ 时间内计算字符串每个后缀与整个字符串的最长公共前缀（LCP）长度。由Gusfield等人推广，该算法是KMP算法的重要补充，在字符串匹配、周期检测、重复子串查找等场景中有广泛应用。
核心思想
对于字符串 $s$，定义 $Z[i]$ 为 $s$ 与从位置 $i$ 开始的后缀 $s[i..n-1]$ 的最长公共前缀长度。Z算法的关键在于维护一个最右匹配的区间 $[l, r]$，利用已计算的信息避免重复比较，从而将整体复杂度降至线性。
Java实现
/**
* Z函数（Z-Algorithm）实现
* 线性时间计算每个后缀与原串的最长公共前缀长度
*/
public class ZFunction {
/**
* 计算字符串s的Z数组
* z[i]表示s[0..n-1]与s[i..n-1]的最长公共前缀长度
* z[0]通常定义为n（整个字符串自身匹配）
*/
public static int[] computeZ(String s) {
int n = s.length();
int[] z = new int[n];
z[0] = n; // z[0]定义为整个字符串长度
// l和r维护当前最右的Z-box区间[l, r]
// 表示s[l..r]与s[0..r-l]完全匹配
int l = 0, r = 0;
for (int i = 1; i < n; i++) {
// 情况1：i在当前Z-box之外，需要从头比较
if (i > r) {
l = r = i;
// 直接暴力扩展匹配
while (r < n && s.charAt(r - l) == s.charAt(r)) {
r++;
}
z[i] = r - l;
r--; // r是最后一个匹配位置，区间是[l, r]
} else {
// 情况2：i在当前Z-box之内，可以利用已有信息
// k是i在Z-box中的对称位置
int k = i - l;
// 情况2a：z[k]的匹配范围完全在Z-box内
// 则z[i]至少等于z[k]
if (z[k] < r - i + 1) {
z[i] = z[k];
} else {
// 情况2b：z[k]的匹配范围超出Z-box
// 需要从r+1开始继续扩展比较
l = i;
while (r < n && s.charAt(r - l) == s.charAt(r)) {
r++;
}
z[i] = r - l;
r--;
}
}
}
return z;
}
/**
* 使用Z函数进行模式匹配
* 在文本text中查找模式pattern的所有出现位置
* 将pattern + '$' + text拼接后计算Z数组
*/
public static java.util.List<Integer> patternMatch(String text, String pattern) {
java.util.List<Integer> result = new java.util.ArrayList<>();
if (pattern.length() > text.length()) {
return result;
}
// 构造拼接字符串: pattern$text
// $是分隔符，不出现在原串中
String combined = pattern + "$" + text;
int[] z = computeZ(combined);
int pLen = pattern.length();
// 在拼接字符串中，pattern之后的每个位置的Z值
// 如果等于pattern长度，说明此处有匹配
for (int i = pLen + 1; i < combined.length(); i++) {
if (z[i] == pLen) {
// 减去pattern长度和分隔符长度得到原串中的起始位置
result.add(i - pLen - 1);
}
}
return result;
}
/**
* 查找字符串的最短周期
* 如果字符串有周期T，则s[i] = s[i+T]对所有有效i成立
*/
public static int findPeriod(String s) {
int n = s.length();
int[] z = computeZ(s);
for (int i = 1; i < n; i++) {
// 如果i是周期候选，需要满足：
// 1. n % i == 0（长度能被周期整除）
// 2. z[i] == n - i（从i开始的后缀与原串前缀完全匹配）
if (n % i == 0 && z[i] == n - i) {
return i;
}
}
return n; // 无更短周期
}
/**
* 统计每个前缀在字符串中出现的次数（包含重叠）
*/
public static int[] prefixOccurrences(String s) {
int n = s.length();
int[] z = computeZ(s);
int[] count = new int[n + 1];
// 统计每个Z值的出现次数
for (int i = 0; i < n; i++) {
count[z[i]]++;
}
// 后缀和：长度>=i的前缀出现次数
for (int i = n - 1; i >= 1; i--) {
count[i] += count[i + 1];
}
// count[i]表示长度为i的前缀作为子串出现的次数
return count;
}
/**
* 计算两个字符串的最长公共前缀长度
*/
public static int longestCommonPrefix(String a, String b) {
String combined = a + "$" + b;
int[] z = computeZ(combined);
// 从a.length()+1开始就是b的Z值
return z[a.length() + 1];
}
/**
* 打印Z数组并可视化匹配情况
*/
public static void printZ(String s) {
int[] z = computeZ(s);
System.out.println("字符串: " + s);
System.out.print("Z数组: ");
for (int v : z) {
System.out.print(v + " ");
}
System.out.println();
// 可视化每个位置的匹配
for (int i = 1; i < s.length(); i++) {
if (z[i] > 0) {
System.out.println("位置 " + i + ": 匹配前缀长度 " + z[i] +
" -> \"" + s.substring(i, i + z[i]) + "\"");
}
}
}
public static void main(String[] args) {
System.out.println("=== Z函数基础计算 ===");
String s1 = "aabcaabxaaaz";
printZ(s1);
System.out.println("\n=== 模式匹配 ===");
String text = "ababcababcabc";
String pattern = "abc";
java.util.List<Integer> matches = patternMatch(text, pattern);
System.out.println("文本: " + text);
System.out.println("模式: " + pattern);
System.out.println("匹配位置: " + matches);
System.out.println("\n=== 周期检测 ===");
String s2 = "abcabcabc";
String s3 = "abcabd";
System.out.println("\"" + s2 + "\" 的最短周期: " + findPeriod(s2));
System.out.println("\"" + s3 + "\" 的最短周期: " + findPeriod(s3));
System.out.println("\n=== 前缀出现次数统计 ===");
String s4 = "aaaa";
int[] occ = prefixOccurrences(s4);
for (int i = 1; i <= s4.length(); i++) {
System.out.println("长度为 " + i + " 的前缀出现次数: " + occ[i]);
}
System.out.println("\n=== 最长公共前缀 ===");
String a = "algorithm";
String b = "algebra";
System.out.println("\"" + a + "\" 和 \"" + b + "\" 的LCP长度: " +
longestCommonPrefix(a, b));
}
}
复杂度分析
| 操作 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| Z数组计算 | $O(n)$ | $O(n)$ | 每个字符最多被比较常数次 |
| 模式匹配 | $O(n + m)$ | $O(n + m)$ | n为文本长，m为模式长 |
| 周期检测 | $O(n)$ | $O(n)$ | 基于Z数组线性扫描 |
| LCP计算 | $O(n + m)$ | $O(n + m)$ | 拼接后计算Z数组 |
算法优势与适用场景
优势：
– 线性时间复杂度，理论最优
– 代码简洁，实现难度低于后缀数组/后缀自动机
– 与KMP互补，某些场景更直观
适用场景：
– 单次文本多模式匹配（比多次KMP更高效）
– 字符串周期性与重复检测
– 计算几何中字符串比较相关的LCP问题
– 压缩算法中的重复子串发现
