每日算法 — 使用java实现Z算法：线性时间字符串前缀匹配

引言

字符串匹配是计算机科学中最基础、最广泛应用的算法问题之一。从文本编辑器的查找替换到搜索引擎的关键词检索，从DNA序列比对到网络入侵检测，高效的字符串算法无处不在。Z算法（Z-Algorithm）是一种能够在O(n)线性时间内完成字符串前缀匹配的经典算法，它不仅代码简洁，而且常数因子极小，在实际工程中比KMP算法更具性能优势。本文将深入讲解Z数组的构造原理，并用Java实现完整的Z算法框架。

问题建模

给定一个长度为n的字符串s，Z算法为每个位置i（1 ≤ i < n）计算一个值Z[i]，表示s[i..n-1]与s[0..n-1]的最长公共前缀（LCP）长度。换言之，Z[i]就是从位置i开始，字符串s与自身前缀相匹配的最长长度。

例如，对于字符串 "abacabadabacabae"：
– Z[0] = 16（整个字符串，通常定义为n或留空）
– Z[1] = 0（"b" 与 "a" 不匹配）
– Z[2] = 1（"a" 与 "a" 匹配1个字符）
– Z[3] = 0（"c" 与 "a" 不匹配）
– Z[4] = 3（"abad" 与 "abac" 匹配 "aba"，长度为3）

核心思想：维护匹配区间 [L, R]

Z算法的高效性来源于一个关键观察：利用已计算的Z值来避免重复比较。

算法维护一个最右匹配区间 [L, R]，表示当前已知的最靠右的、与前缀匹配的子串区间。对于新位置i：

1. 如果 i > R：说明当前位置不在任何已知匹配区间内，需要从头开始暴力匹配，然后更新 [L, R]。
2. 如果 i ≤ R：令 k = i - L，则 s[i..R] 与 s[k..R-L] 相同。
3. 若 Z[k] < R - i + 1：则 Z[i] = Z[k]，无需额外比较。
4. 若 Z[k] ≥ R - i + 1：则 Z[i] 至少为 R - i + 1，需要从 R + 1 继续向后匹配，然后更新 [L, R]。

Java实现

import java.util.*;

/**
 * Z算法实现：线性时间字符串前缀匹配
 * 时间复杂度：O(n)，空间复杂度：O(n)
 */
public class ZAlgorithm {

    /**
     * 计算字符串s的Z数组
     * @param s 输入字符串
     * @return Z数组，Z[i]表示s[i..]与s[0..]的最长公共前缀长度
     */
    public static int[] computeZ(String s) {
        int n = s.length();
        int[] Z = new int[n];
        Z[0] = n; // 位置0的Z值定义为整个字符串长度

        int L = 0, R = 0; // 维护最右匹配区间[L, R]

        for (int i = 1; i < n; i++) {
            // 情况1：i在当前匹配区间右侧，需要从头匹配
            if (i > R) {
                L = R = i;
                // 从位置R开始向后匹配
                while (R < n && s.charAt(R) == s.charAt(R - L)) {
                    R++;
                }
                Z[i] = R - L; // 匹配长度
                R--; // R指向匹配区间的最后一个字符
            } else {
                // 情况2：i在当前匹配区间内，利用已计算的Z值
                int k = i - L; // s[i..R] 对应 s[k..R-L]

                // 子情况2a：Z[k]的值完全在区间内，直接复用
                if (Z[k] < R - i + 1) {
                    Z[i] = Z[k];
                } else {
                    // 子情况2b：Z[k]可能超出区间，需要从R+1继续匹配
                    L = i;
                    R++; // R已经匹配到，从R+1开始
                    while (R < n && s.charAt(R) == s.charAt(R - L)) {
                        R++;
                    }
                    Z[i] = R - L;
                    R--;
                }
            }
        }

        return Z;
    }

    /**
     * 使用Z算法进行模式串匹配
     * 构造文本T = pattern + '$' + text，计算Z数组
     * 当Z[i] == pattern.length()时，表示在text的对应位置找到匹配
     * @param text 主文本
     * @param pattern 模式串
     * @return 所有匹配起始位置列表
     */
    public static List<Integer> findOccurrences(String text, String pattern) {
        List<Integer> result = new ArrayList<>();
        if (pattern.isEmpty() || pattern.length() > text.length()) {
            return result;
        }

        // 构造组合字符串：pattern + 分隔符 + text
        // 分隔符必须是pattern和text中都不出现的字符
        String combined = pattern + "#" + text;
        int[] Z = computeZ(combined);
        int m = pattern.length();

        // 遍历text部分的Z值
        for (int i = m + 1; i < Z.length; i++) {
            if (Z[i] == m) {
                // 匹配成功，计算在text中的实际位置
                result.add(i - m - 1);
            }
        }

        return result;
    }

    /**
     * 扩展应用：计算字符串所有前缀的出现次数
     * 利用Z数组统计每个前缀作为子串出现的次数
     */
    public static int[] prefixOccurrenceCount(String s) {
        int n = s.length();
        int[] Z = computeZ(s);
        int[] count = new int[n + 1];

        // Z[i] >= k 表示长度为k的前缀在位置i出现
        for (int i = 0; i < n; i++) {
            count[Z[i]]++;
        }

        // 后缀和：count[k]表示长度>=k的前缀出现次数
        // 反过来求精确长度
        for (int i = n - 1; i >= 1; i--) {
            count[i] += count[i + 1];
        }

        // count[i]现在表示长度为i的前缀至少出现一次的次数
        return count;
    }

    /**
     * 扩展应用：寻找字符串的最短周期
     * 如果s长度为n，且Z[k] >= n - k，则k是一个周期
     */
    public static int findShortestPeriod(String s) {
        int n = s.length();
        int[] Z = computeZ(s);

        for (int p = 1; p <= n / 2; p++) {
            if (n % p == 0 && Z[p] >= n - p) {
                return p;
            }
        }
        return n; // 无周期，返回自身长度
    }

    public static void main(String[] args) {
        // 测试1：基本Z数组计算
        String s1 = "abacabadabacabae";
        int[] Z1 = computeZ(s1);
        System.out.println("字符串: " + s1);
        System.out.print("Z数组: ");
        for (int z : Z1) {
            System.out.print(z + " ");
        }
        System.out.println();

        // 测试2：模式匹配
        String text = "abacabadabacabaeabacabad";
        String pattern = "abacabad";
        List<Integer> matches = findOccurrences(text, pattern);
        System.out.println("\n文本: " + text);
        System.out.println("模式: " + pattern);
        System.out.println("匹配位置: " + matches);

        // 测试3：周期检测
        String periodic = "abcabcabcabc";
        int period = findShortestPeriod(periodic);
        System.out.println("\n字符串: " + periodic);
        System.out.println("最短周期: " + period);

        // 测试4：边界情况
        String single = "a";
        int[] Z2 = computeZ(single);
        System.out.println("\n单字符Z数组: " + Arrays.toString(Z2));

        String same = "aaaaa";
        int[] Z3 = computeZ(same);
        System.out.println("重复字符Z数组: " + Arrays.toString(Z3));
    }
}

复杂度分析

• 时间复杂度：O(n)。每个字符最多被比较两次（一次在扩展R时，一次在Z[k]超限时），因此总比较次数不超过2n。
• 空间复杂度：O(n)。需要存储Z数组，以及组合字符串（模式匹配场景）。

与KMP算法的对比

总结

Z算法以其优雅的区间复用思想和极简的代码实现，成为字符串算法领域的瑰宝。本文从Z数组的定义出发，详细剖析了 [L, R] 区间的维护策略，提供了完整的Java实现，并展示了模式匹配、周期检测等扩展应用。掌握Z算法，不仅能提升字符串处理能力，更能深化对线性时间算法设计思想的认知。