深入理解Z算法（Java语言实现字符串高效匹配）

为什么使用Z算法？

相比暴力匹配（时间复杂度 O(n²)），Z算法可以在 O(n) 时间内完成整个 Z 数组的构建，效率极高。它常被用于解决以下问题：

• 在一个大文本中查找某个模式串的所有出现位置
• 判断一个字符串是否由另一个字符串重复构成
• 快速计算字符串的前缀函数相关性质

Java 实现 Z 算法

下面我们用 Java 编写一个完整的 Z 算法实现。代码包含详细注释，便于理解。

public class ZAlgorithm {    /**     * 构建字符串 s 的 Z 数组     * @param s 输入字符串     * @return Z 数组     */    public static int[] computeZArray(String s) {        int n = s.length();        int[] z = new int[n];                // Z[0] 通常定义为 0 或者 n（根据用途不同），这里设为 0        z[0] = 0;                // 定义 Z-box 的左右边界 [l, r]        int l = 0, r = 0;                for (int i = 1; i < n; i++) {            // 情况1：i 在当前 Z-box 范围内            if (i <= r) {                // 利用对称性，避免重复比较                z[i] = Math.min(r - i + 1, z[i - l]);            }                        // 尝试向右扩展 Z[i]            while (i + z[i] < n && s.charAt(z[i]) == s.charAt(i + z[i])) {                z[i]++;            }                        // 更新 Z-box 边界            if (i + z[i] - 1 > r) {                l = i;                r = i + z[i] - 1;            }        }                return z;    }    // 测试示例    public static void main(String[] args) {        String text = "aabcaabxaa";        int[] z = computeZArray(text);                System.out.println("字符串: " + text);        System.out.print("Z 数组: ");        for (int val : z) {            System.out.print(val + " ");        }        // 输出: 0 1 0 0 2 1 0 0 1 0    }}  

算法原理详解

Z算法的关键在于维护一个“Z-box”——即当前已知的最靠右的匹配区间 [l, r]。这个区间表示从位置 l 开始有一段长度为 (r - l + 1) 的子串，它与字符串前缀完全匹配。

当处理新位置 i 时：

• 如果 i ≤ r，说明 i 在 Z-box 内，我们可以利用对称性直接获得部分信息（即 z[i] ≥ z[i - l]）；
• 否则，必须从头开始逐字符比较。

这种“跳跃式”比较避免了大量重复工作，从而保证了线性时间复杂度。

应用场景举例

假设我们要在文本 T 中查找模式 P 的所有出现位置。可以构造新字符串 S = P + "$" + T（$ 是分隔符，确保不会跨过边界匹配），然后对 S 运行 Z 算法。所有满足 Z[i] == len(P) 且 i > len(P) 的位置，就是 P 在 T 中的匹配起始位置。

总结

通过本教程，你已经掌握了 Z算法 的基本概念、Java 实现方式及其在字符串匹配中的应用。Z算法不仅高效，而且逻辑清晰，是学习高级字符串算法的重要一步。无论是面试准备还是实际开发，理解Java Z算法实现和前缀函数思想都将为你打下坚实基础。

动手试试吧！修改上面的代码，尝试在自己的项目中使用 Z 算法解决实际问题。