每日算法 — 使用java实现Z函数：线性时间字符串前缀匹配与高效模式搜索

可莉爸爸 AI算法

引言

在字符串处理领域，如何快速判断一个字符串的某个后缀与前缀的相似程度，是诸多算法问题的基础。Z函数（Z-Algorithm）正是解决这一问题的利器——它能够在 O(n) 线性时间内，计算出字符串每个位置开始的后缀与整个字符串的最长公共前缀长度。相比需要预处理前缀函数的 KMP 算法，Z函数的构造过程更加直观，且在字符串匹配、文本去重、基因序列比对等场景中表现优异。本文将用 Java 完整实现 Z 函数，并展示其在游戏开发中快速检测聊天关键词的实际应用。

Z函数的定义

对于长度为 n 的字符串 s，Z函数定义为一个长度为 n 的数组 z，其中：

  • z[0] = 0（或 n，视约定而定，本文取 0）
  • 对于 i > 0，z[i] 表示字符串 s 与从位置 i 开始的后缀 s[i..n-1] 的最长公共前缀长度

例如，对于字符串 s = "ababab"：

i 后缀 最长公共前缀 z[i]
0 ababab – 0
1 babab 无 0
2 abab abab 4
3 bab 无 0
4 ab ab 2
5 b 无 0

得到 z 数组为：[0, 0, 4, 0, 2, 0]

算法核心思想

Z函数的高效计算依赖于一个关键观察：维护一个当前最右匹配区间 [l, r]。

当我们已经计算出 z[0..i-1]，并且知道某个区间 [l, r] 是此前匹配的最右边界（即 r 最大）时，对于位置 i：

  1. 如果 i <= r：说明位置 i 落在了已知的匹配区间内。此时可以利用已计算出的 z[i-l] 来初始化 z[i]，避免重复比较。

  2. 令 k = i - l，则 z[i] 至少可以从 min(z[k], r - i + 1) 开始（因为超出 r 的部分无法保证匹配）。

  3. 如果 i > r：说明位置 i 不在任何已知匹配区间内，需要从 0 开始逐个字符比较。

  4. 扩展匹配：无论上述哪种情况，都需要从当前候选位置继续向后比较，尝试扩展匹配长度，并更新 [l, r] 区间。

这种”利用已知信息避免重复计算”的策略，确保了整体时间复杂度为 O(n)。

Java实现

核心Z函数计算

public class ZAlgorithm {

    /**
     * 计算字符串的Z函数数组
     * @param s 输入字符串
     * @return Z函数数组，z[i]表示s与s[i..]的最长公共前缀长度
     */
    public static int[] computeZ(String s) {
        int n = s.length();
        int[] z = new int[n];
        // z[0]通常定义为0或n，本文采用0
        z[0] = 0;

        // l和r维护当前最右匹配区间的左右边界
        int l = 0, r = 0;

        for (int i = 1; i < n; i++) {
            // 情况1：i在当前匹配区间[l, r]内，可以利用已有计算结果
            if (i <= r) {
                // z[i-l]对应的是s[0..]与s[i-l..]的匹配长度
                // 但这个长度不能超过r-i+1（因为r之后的字符尚未验证）
                z[i] = Math.min(r - i + 1, z[i - l]);
            }

            // 情况2：从z[i]开始继续向后匹配，尝试扩展
            // 即使i>r，z[i]初始为0，这里也会正常工作
            while (i + z[i] < n && s.charAt(z[i]) == s.charAt(i + z[i])) {
                z[i]++;
            }

            // 如果当前匹配区间更靠右，更新[l, r]
            if (i + z[i] - 1 > r) {
                l = i;
                r = i + z[i] - 1;
            }
        }

        return z;
    }

    /**
     * 打印Z函数数组（调试用）
     */
    public static void printZArray(int[] z) {
        System.out.print("Z数组: ");
        for (int val : z) {
            System.out.print(val + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        // 测试用例1：简单重复模式
        String s1 = "ababab";
        int[] z1 = computeZ(s1);
        System.out.println("字符串: " + s1);
        printZArray(z1);
        // 期望输出: 0 0 4 0 2 0

        // 测试用例2：部分前缀匹配
        String s2 = "aaabaaa";
        int[] z2 = computeZ(s2);
        System.out.println("字符串: " + s2);
        printZArray(z2);
        // 期望输出: 0 2 1 0 2 1 0

        // 测试用例3：无重复前缀
        String s3 = "abcdef";
        int[] z3 = computeZ(s3);
        System.out.println("字符串: " + s3);
        printZArray(z3);
        // 期望输出: 0 0 0 0 0 0
    }
}

字符串匹配应用

利用Z函数进行模式匹配的思路是：将模式串 p 和文本串 t 用分隔符连接成 p + '#' + t（# 是不出现在两个串中的特殊字符），然后计算连接后字符串的Z函数。当某个位置的Z值等于模式串长度时，即找到一个匹配。

public class ZPatternMatch {

    /**
     * 使用Z函数进行模式匹配
     * @param text 文本串
     * @param pattern 模式串
     * @return 所有匹配的起始位置列表
     */
    public static java.util.List<Integer> findPattern(String text, String pattern) {
        java.util.List<Integer> result = new java.util.ArrayList<>();

        if (pattern.isEmpty() || pattern.length() > text.length()) {
            return result;
        }

        // 构造连接串: pattern + '#' + text
        // '#' 选择一个不会出现在原串中的分隔符
        String separator = "#";
        // 更安全的做法：使用一个确定不会出现的Unicode字符
        // 这里为了简化，假设'#'不出现在输入中
        // 实际工程中可使用两个不会同时出现的字符或随机化分隔符
        String combined = pattern + separator + text;

        int[] z = ZAlgorithm.computeZ(combined);
        int patternLen = pattern.length();

        // 遍历text部分对应的Z值
        for (int i = patternLen + separator.length(); i < combined.length(); i++) {
            if (z[i] == patternLen) {
                // 找到匹配，计算在text中的起始位置
                int matchPos = i - patternLen - separator.length();
                result.add(matchPos);
            }
        }

        return result;
    }

    /**
     * 安全的模式匹配：自动选择分隔符
     */
    public static java.util.List<Integer> findPatternSafe(String text, String pattern) {
        java.util.List<Integer> result = new java.util.ArrayList<>();

        if (pattern.isEmpty() || pattern.length() > text.length()) {
            return result;
        }

        // 找到一个不出现在text和pattern中的字符作为分隔符
        char separator = '\0';
        for (char c = 1; c < 256; c++) {
            if (text.indexOf(c) == -1 && pattern.indexOf(c) == -1) {
                separator = c;
                break;
            }
        }

        String combined = pattern + separator + text;
        int[] z = ZAlgorithm.computeZ(combined);
        int patternLen = pattern.length();

        for (int i = patternLen + 1; i < combined.length(); i++) {
            if (z[i] == patternLen) {
                int matchPos = i - patternLen - 1;
                result.add(matchPos);
            }
        }

        return result;
    }

    public static void main(String[] args) {
        String text = "ababaababab";
        String pattern = "abab";

        java.util.List<Integer> matches = findPattern(text, pattern);
        System.out.println("文本: " + text);
        System.out.println("模式: " + pattern);
        System.out.println("匹配位置: " + matches);
        // 期望: 位置0和位置5（ababaababab中，abab出现在开头和第5位）
    }
}

游戏聊天关键词过滤系统

在多人在线游戏中，聊天系统的关键词过滤是常见需求。利用Z函数，我们可以高效地检测多个敏感词是否在玩家消息中出现。

import java.util.*;

/**
 * 基于Z函数的游戏聊天关键词过滤器
 * 支持多模式串的高效匹配
 */
public class ChatFilter {

    private final List<String> keywords;
    private final String separator;

    public ChatFilter(List<String> keywords) {
        this.keywords = new ArrayList<>(keywords);
        // 选择一个安全分隔符
        this.separator = findSafeSeparator(keywords);
    }

    /**
     * 找到一个不会出现在任何关键词中的字符作为分隔符
     */
    private String findSafeSeparator(List<String> keywords) {
        for (char c = 1; c < 65535; c++) {
            final char ch = c;
            boolean safe = keywords.stream().allMatch(k -> k.indexOf(ch) == -1);
            if (safe) {
                return String.valueOf(c);
            }
        }
        // 理论上不会发生，所有字符都用完了
        throw new IllegalStateException("无法找到安全分隔符");
    }

    /**
     * 检测消息中是否包含任何敏感词
     * @param message 玩家消息
     * @return 匹配到的敏感词列表
     */
    public List<String> detectKeywords(String message) {
        List<String> detected = new ArrayList<>();

        for (String keyword : keywords) {
            if (keyword.isEmpty()) continue;

            // 使用Z函数检测单个关键词
            String combined = keyword + separator + message;
            int[] z = ZAlgorithm.computeZ(combined);
            int kwLen = keyword.length();
            int sepLen = separator.length();

            boolean found = false;
            for (int i = kwLen + sepLen; i < combined.length() && !found; i++) {
                if (z[i] == kwLen) {
                    detected.add(keyword);
                    found = true;
                }
            }
        }

        return detected;
    }

    /**
     * 将消息中的敏感词替换为*
     * @param message 原始消息
     * @return 过滤后的消息
     */
    public String filterMessage(String message) {
        char[] chars = message.toCharArray();

        for (String keyword : keywords) {
            if (keyword.isEmpty()) continue;

            String combined = keyword + separator + message;
            int[] z = ZAlgorithm.computeZ(combined);
            int kwLen = keyword.length();
            int sepLen = separator.length();

            for (int i = kwLen + sepLen; i < combined.length(); i++) {
                if (z[i] == kwLen) {
                    int pos = i - kwLen - sepLen;
                    for (int j = 0; j < kwLen; j++) {
                        chars[pos + j] = '*';
                    }
                }
            }
        }

        return new String(chars);
    }

    public static void main(String[] args) {
        List<String> keywords = Arrays.asList("作弊", "外挂", "辱骂");
        ChatFilter filter = new ChatFilter(keywords);

        String[] messages = {
            "大家好，今天天气不错",
            "有人在用作弊工具",
            "请不要使用外挂程序",
            "文明游戏，禁止辱骂"
        };

        for (String msg : messages) {
            List<String> detected = filter.detectKeywords(msg);
            String filtered = filter.filterMessage(msg);
            System.out.println("原文: " + msg);
            System.out.println("检测: " + detected);
            System.out.println("过滤: " + filtered);
            System.out.println();
        }
    }
}

复杂度分析

时间复杂度

Z函数计算：O(n)，其中 n 是字符串长度。

证明：外层循环遍历每个位置一次。内层的 while 循环每次成功匹配都会使 r 右移，而 r 总共最多右移 n 次。因此总体时间复杂度为线性。

字符串匹配：设文本长度为 n，模式长度为 m。构造连接串长度为 m + 1 + n，Z函数计算时间为 O(m + n)。

多关键词过滤：设有 k 个关键词，平均长度为 m，消息长度为 n。总时间为 O(k * (m + n))。若需要进一步优化，可结合 Aho-Corasick 算法实现 O(n + 总关键词长度) 的多模式匹配。

空间复杂度

Z函数计算：O(n)，用于存储Z数组。

字符串匹配：O(m + n)，用于存储连接串和Z数组。

与KMP算法的对比

特性 Z函数 KMP
预处理时间 O(n) O(m)
匹配时间 O(m + n) O(m + n)
空间复杂度 O(m + n) O(m)
代码复杂度 较直观 前缀函数较难理解
多模式匹配 需分别处理 需分别处理
获取所有匹配位置 天然支持 需额外处理

Z函数的优势在于代码实现更加直观，且天然支持获取所有匹配位置。KMP在空间上略有优势，但前缀函数的理解门槛较高。在实际工程中，两种算法可以根据场景灵活选用。

扩展应用

最长回文子串的Z函数解法

将字符串 s 反转得到 s'，则 s 的某个子串是回文串，当且仅当它与 s' 中对应位置的子串互为反转。利用Z函数可以在 O(n) 时间内找到最长回文前缀和最长回文后缀，结合 Manacher 算法可以实现完整的最长回文子串求解。

字符串周期检测

若字符串 s 存在周期 p（即 s[i] = s[i+p] 对所有有效 i 成立），则 z[p] = n - p。利用Z函数可以快速检测字符串的最小周期。

文本去重与相似度计算

在大量文本数据中，利用Z函数可以快速计算两个字符串的公共前缀长度，进而用于文本去重、相似度计算等任务。

总结

Z函数是一个简洁而强大的字符串工具，其核心思想——维护最右匹配区间以避免重复计算——体现了算法设计中”利用已知信息”的精髓。本文从定义出发，逐步讲解了Z函数的线性时间构造原理，给出了完整的Java实现，并展示了其在字符串匹配和游戏聊天过滤中的实际应用。掌握Z函数，不仅能加深对字符串算法的理解，也为解决各类文本处理问题提供了一个高效的工具。

Tagged with: