一、从暴力匹配看 Z 数组的价值

在主串中查找模式串，最直接的做法是逐位对齐、逐字符比较。一旦失配就把模式串整体右移一位重新开始，最坏情况下（例如主串是 "aaaaa"、模式串是 "aaaab"）每个位置都要比到模式串末尾才失败，复杂度退化为 O(n×m)。KMP 通过前缀函数把已经比较过的信息保留下来，把复杂度压到 O(n+m)；Z 算法是同一思想的另一种表达，它不预处理模式串，而是预处理拼接后的整串，思路更直观，代码也更短。

Z 数组的定义很明确：对长度为 n 的字符串 s，Z[i] 表示 s 本身与从 i 位置开始的后缀的"最长公共前缀"长度。换句话说，Z[i] 就是"从 i 开始往前看，最多能连续匹配回 s 开头多少个字符"。约定 Z[0] = n（自身与自身完全相同）。

以 s = "abacaba" 为例：从下标 4 开始的后缀是 "aba"，与串首 "aba" 完全相同，所以 Z[4] = 3；下标 2 的后缀是 "acaba"，首字符 a 与串首相同但第二个字符 c 不同，所以 Z[2] = 1；下标 1 的后缀首字符是 b，与串首 a 不同，Z[1] = 0。

二、Z-box：让每个字符只被比较常数次

2.1 维护一个最靠右的匹配区间

如果对每个 i 都暴力向后比较，复杂度依然是 O(n²)。Z 算法之所以能线性，靠的是复用已经算出的匹配信息。具体做法是维护一个区间 [l, r]，它表示"目前已经找到的、右端点最靠右的、与串首完全匹配的子串"——即 s[l..r] 与 s[0..r-l] 完全相同。

当计算到位置 i 时，如果 i 落在 r 以内（i <= r），那么 s[i..r] 这一段必然与 s[i-l..r-l] 完全相同，这是由 [l, r] 的定义直接得到的。于是 Z[i] 至少可以先取到 Z[i-l] 的值，这里就出现了核心的加速机会。

2.2 三种情形

设已知 Z[i-l] 的值为 k，可用长度上限是 r-i+1（超出这个范围的部分还没有验证过），于是先令 Z[i] = min(r-i+1, Z[i-l])。接着分情形讨论：

• 情形一：i > r。区间用不上，只能从 Z[i]=0 开始暴力比较。

• 情形二：Z[i-l] < r-i+1。说明 i-l 处的匹配在区间内就结束了，那么在 i 处也会同样结束，Z[i] 直接等于 Z[i-l]，不需要再比较，直接跳过 while 循环。

• 情形三：Z[i-l] >= r-i+1。说明匹配至少延续到 r，但 r 之后的内容未知，必须从 r+1 开始继续比较，这正是 while 循环承担的工作。

这三种情形正好被一行 Math.min 加一个 while 循环全部覆盖：min 处理情形二的上界，while 处理情形三的延伸，情形一则自然退化为从 0 开始扩。代码因此显得格外简洁。

2.3 为什么这是线性的

关键在于 r 只增不减。每次 while 循环成功一次，r 就右移一位；而 r 最多从 0 走到 n，所以 while 在整个算法中的总成功次数不超过 n 次。while 的失败比较每个 i 至多发生一次，共 n 次。两者相加仍是 O(n)，这就是 Z 算法线性复杂度的直观解释。

2.4 区间更新

每算完一个 Z[i]，若 i + Z[i] - 1 超过了当前的 r，说明找到了一个更靠右的匹配区间，就令 l = i、r = i + Z[i] - 1。注意 Z[i] 为 0 时 i+Z[i]-1 = i-1，不会大于等于 i，因此不会误更新区间。

三、代码整体架构

ZAlgorithm 类共四个方法。getZArray 是核心，用 l、r 双指针维护 Z-box；search 把模式串与主串用哨兵字符 # 拼成 pattern#text，在拼接串上跑一次 Z 数组，凡是 Z 值等于模式串长度的地方就是一个匹配起点；longestCommonSubstring 用 a#b 的拼法求两串最长公共子串；main 演示三组测试。

四、核心代码逐段解析

4.1 getZArray

方法先处理空串（返回长度为 0 的数组），再设 Z[0] = n，并把 l、r 初始化为 0。进入循环后，第一段 if (i <= r) 正是 2.2 节情形二与情形三的分流点：用 Math.min(r - i + 1, Z[i - l]) 给出一个安全的下界。

第二段 while 是唯一的"真比较"：条件是 i + Z[i] < n 保证不越界，s.charAt(Z[i]) == s.charAt(i + Z[i]) 则是比较"串首偏移 Z[i] 处"与"当前位置偏移 Z[i] 处"是否相同，相同就自增。这里巧妙地把"串首的第几个字符"直接用 Z[i] 当成了下标，省去了额外的指针变量。

第三段更新区间。整个循环体只有十几行，却完成了 KMP 前缀函数同样的工作。

4.2 search 模式匹配

拼接串 pattern + "#" + text 的设计有两重作用。第一，哨兵 # 把模式串与主串隔开，保证任何 Z 值都不会"跨过"边界去匹配主串里的内容，也就不会出现长度超过模式串的假匹配。第二，Z 值等于模式串长度，就意味着从该位置起恰好完整复制了模式串——这正是匹配成功。

循环从 pLen+1 开始，跳过模式串自身与哨兵位置，只扫描主串部分；返回下标时用 i - pLen - 1 换算回原主串的坐标。哨兵字符必须保证不出现在 pattern 与 text 中，代码注释里提到的 \0（空字符）就是安全的兜底选择。

4.3 longestCommonSubstring 最长公共子串

求两个串的最长公共子串，本质是"在 B 中找一段，它恰好也是 A 的某个前缀的延伸"。拼成 a#b 之后，B 部分每个位置的 Z 值就表示"从这里开始能与 A 的串首连续匹配多长"，取最大值即为最长公共子串长度。

循环只扫描 B 部分（从 a.length()+1 开始），记录最大 Z 值与对应位置 endPos，最后在 B 中截取。这里需要留意两点：一是 Z 值被哨兵限制在 a.length() 以内，天然不会超出 A 的长度；二是当两串完全没有公共字符时，maxLen 保持 0、endPos 保持初始值 0，直接代入子串截取会算出负的下标——这一点在后文第八节作为实测缺陷专门讨论。

4.4 main 测试

main 分三部分：先看 "abacaba" 的 Z 数组，注释里逐位列出了每个后缀应有的答案，便于对照；再做一次模式匹配，主串选用 "abacabaabacaba"，模式串 "aba"；最后求 "abacaba" 与 "xabacabax" 的最长公共子串。

五、完整源代码

以下为完整可运行代码，可直接复制。

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class ZAlgorithm {

    /**
     * 计算 Z 数组
     * Z[i] 表示字符串 s 与其从 i 开始的后缀的最长公共前缀（LCP）长度。
     * 规定 Z[0] = s.length()。
     */
    public static int[] getZArray(String s) {
        int n = s.length();
        int[] Z = new int[n];
        if (n == 0) return Z;

        Z[0] = n;
        int l = 0, r = 0; // 维护当前匹配最靠右的区间 [l, r]

        for (int i = 1; i < n; i++) {
            // 1. 利用之前的匹配区间加速
            if (i <= r) {
                Z[i] = Math.min(r - i + 1, Z[i - l]);
            }

            // 2. 暴力扩展（如果还能往外扩的话）
            while (i + Z[i] < n && s.charAt(Z[i]) == s.charAt(i + Z[i])) {
                Z[i]++;
            }

            // 3. 更新最靠右的区间 [l, r]
            if (i + Z[i] - 1 > r) {
                l = i;
                r = i + Z[i] - 1;
            }
        }
        return Z;
    }

    // ==================== 核心应用 ====================

    /**
     * 应用 1：在文本串 text 中查找所有的模式串 pattern
     * 时间复杂度 O(n + m)
     */
    public static List<Integer> search(String text, String pattern) {
        List<Integer> result = new ArrayList<>();
        if (pattern.isEmpty()) return result;

        // 构造拼接字符串：pattern + '#' + text
        // 注意：'#' 必须是原串中不存在的字符。如果是任意 ASCII，可使用 '\0'
        String concat = pattern + "#" + text;
        int[] Z = getZArray(concat);
        int pLen = pattern.length();

        // 遍历 Z 数组，寻找匹配
        for (int i = pLen + 1; i < concat.length(); i++) {
            // 如果 Z 值等于模式串长度，说明匹配成功
            if (Z[i] == pLen) {
                // 计算在 text 中的起始下标：i - pLen - 1
                result.add(i - pLen - 1);
            }
        }
        return result;
    }

    /**
     * 应用 2：求两个字符串 A 和 B 的最长公共子串 (LCS)
     * （注意这里求的是 Substring，不是 Subsequence）
     */
    public static String longestCommonSubstring(String a, String b) {
        // 也可以用 Z 算法做：A + '#' + B，找 Z 的最大值
        // 但要注意区分是从 A 还是 B 来的
        String concat = a + "#" + b;
        int[] Z = getZArray(concat);
        int maxLen = 0, endPos = 0;

        for (int i = a.length() + 1; i < concat.length(); i++) {
            if (Z[i] > maxLen) {
                maxLen = Z[i];
                endPos = i;
            }
        }
        // endPos 是匹配串的结束位置
        return b.substring(endPos - a.length() - 1, endPos - a.length() - 1 + maxLen);
    }

    // ==================== 测试主程序 ====================

    public static void main(String[] args) {
        System.out.println("========== 1. Z 数组基础测试 ==========");
        String s = "abacaba";
        int[] z = getZArray(s);
        System.out.println("原串: " + s);
        System.out.println("Z 数组: " + Arrays.toString(z));
        // 期望:
        // 后缀 0: abacaba -> 7
        // 后缀 1: bacaba  -> 0
        // 后缀 2: acaba   -> 1 (a)
        // 后缀 3: caba    -> 0
        // 后缀 4: aba     -> 3 (aba)
        // 后缀 5: ba      -> 0
        // 后缀 6: a       -> 1 (a)

        System.out.println("\n========== 2. 字符串模式匹配 ==========");
        String text = "abacabaabacaba";
        String pattern = "aba";
        List<Integer> matches = search(text, pattern);
        System.out.println("文本串: " + text);
        System.out.println("模式串: " + pattern);
        System.out.println("匹配位置: " + matches);
        // 期望: [0, 4, 8, 12]

        System.out.println("\n========== 3. 最长公共子串 (LCS) ==========");
        String s1 = "abacaba";
        String s2 = "xabacabax";
        System.out.println("A: " + s1);
        System.out.println("B: " + s2);
        System.out.println("最长公共子串: " + longestCommonSubstring(s1, s2));
        // 期望: abacaba
    }
}

六、运行结果

在本机 JDK 环境实际编译运行，完整输出如下：

========== 1. Z 数组基础测试 ==========
原串: abacaba
Z 数组: [7, 0, 1, 0, 3, 0, 1]
 
========== 2. 字符串模式匹配 ==========
文本串: abacabaabacaba
模式串: aba
匹配位置: [0, 4, 7, 11]
 
========== 3. 最长公共子串 (LCS) ==========
A: abacaba
B: xabacabax
最长公共子串: abacaba

第一组的 Z 数组与代码注释里逐位列出的答案完全一致：下标 4 处 "aba" 得 3，下标 2 和 6 处只剩首字符匹配得 1，其余为 0。第三组的最长公共子串也如预期得到 "abacaba"，它确实出现在 B 的第 1 位，长度 7。

第二组需要特别说明，匹配位置是 [0, 4, 7, 11]，而代码注释里写的期望值是 [0, 4, 8, 12]，两者不一致。这属于注释里的预期值写错了，不是代码出错，下文第八节会给出逐位核对的过程。

七、多组用例验证

为确认实现不是只在样例上凑巧正确，又跑了多组具有代表性的输入。

7.1 Z 数组

其中 "aabcaabxaaaz" 是 Z 算法（扩展 KMP）教程里的经典标准用例，其结果可与公开资料逐位对照。

字符串	长度	Z 数组
abacaba	7	[7, 0, 1, 0, 3, 0, 1]
aaaaa	5	[5, 4, 3, 2, 1]
ababab	6	[6, 0, 4, 0, 2, 0]
abcabcabc	9	[9, 0, 0, 6, 0, 0, 3, 0, 0]
aabcaabxaaaz	12	[12, 1, 0, 0, 3, 1, 0, 0, 2, 2, 1, 0]
a	1	[1]

"aaaaa" 得到递减的 [5,4,3,2,1]，是 Z 算法最典型的退化情形，此时每个后缀都与串首高度重合，也正好能检验区间复用的正确性；"abcabcabc" 得到 [9,0,0,6,0,0,3,0,0]，三个 3 的倍数位置周期性出现，符合预期。

7.2 模式匹配

主串	模式串	匹配位置
abacabaabacaba	aba	[0, 4, 7, 11]
abcabcabc	abc	[0, 3, 6]
abcabcabc	bca	[1, 4]
abc	abc	[0]
abc	zzzz	[]

四组有效用例的匹配点全部正确，模式串长于主串时返回空列表，说明哨兵拼接与边界判断都是稳的。另外用 Python 独立实现了 Z 算法与暴力子串匹配，对上述用例交叉复核，结论一致。

八、实测与注释不符的两处

8.1 模式匹配的期望注释写错了

主串 "abacabaabacaba" 共 14 个字符，逐位列出如下：

下标:  0  1  2  3  4  5  6  7  8  9 10 11 12 13
字符:  a  b  a  c  a  b  a  a  b  a  c  a  b  a
取3位: aba bac aca cab aba baa aab aba bac aca cab aba

可以看到以 "aba" 开头的窗口只出现在 0、4、7、11 这四个位置。注释里写的 8 和 12 两个位置，取三位分别是 "bac" 和 "ba?"，首字符就不是 a，根本不可能成为匹配起点。因此代码算出的 [0, 4, 7, 11] 是正确的，注释里的 [0, 4, 8, 12] 属于笔误。修正办法很简单：把注释改成 [0, 4, 7, 11] 即可，不影响任何逻辑。

8.2 最长公共子串在无公共字符时会崩

longestCommonSubstring 在两串完全没有公共字符时会抛出异常，实测结果如下：

LCS(hello, world) -> java.lang.StringIndexOutOfBoundsException:
                     begin -6, end -6, length 5

根因在于 maxLen 与 endPos 的初值。当两个串没有任何公共字符时，循环里 Z[i] > maxLen 永远不会成立（Z 值全是 0），maxLen 保持 0、endPos 保持 0。代入 return 表达式时，起始下标变成 0 - a.length() - 1，对 "hello" 就是 -6，而 substring 不允许负下标，于是抛出越界异常。空串参与运算时同样会触发：a 为空串时起始下标是 -1。

修复只需在截取前加一个短路判断：当 maxLen 为 0 时直接返回空串，同时对入参空串提前处理。修改后实测七组用例全部正常：

A	B	修复后返回
abacaba	xabacabax	abacaba
abcdef	abcxyz	abc
hello	world	（空串）
abc	xyz	（空串）
（空串）	abc	（空串）
abc	（空串）	（空串）
aaa	aa	aa

修复后的关键代码如下，只需加两行判断，其余逻辑不动：

if (a.isEmpty() || b.isEmpty()) return "";   // 入参空串短路
...
if (maxLen == 0) return "";                 // 无公共子串短路
int startInB = endPos - a.length() - 1;
return b.substring(startInB, startInB + maxLen);

顺带说明，"aaa" 与 "aa" 的最长公共子串是 "aa" 而不是 "aaa"，这是子串定义决定的：公共子串必须是两串各自的连续片段，长度不能超过较短的那个。

九、复杂度分析

方法	时间	空间	说明
getZArray	O(n)	O(n)	r 单调右移，while 总成功次数不超过 n
search	O(n+m)	O(n+m)	拼接串长度 n+m+1，一次 Z 数组 + 一次线性扫描
longestCommonSubstring	O(n+m)	O(n+m)	同上，额外只在 B 中截取一次

对比 KMP：两者时间空间同阶，KMP 预处理模式串的 next 数组，Z 算法预处理拼接串。Z 算法的优势是代码更短、思路更统一（匹配、LCS、周期检测都用同一套），劣势是每次查询都要新建一个长度 n+m 的拼接串，如果要在同一主串上查多个模式串，KMP 只需预处理一次模式串，而 Z 算法每个模式串都要重算，这在多模式场景下反而不划算。

十、知识点总结

要点	说明
Z 数组定义	Z[i] 为 s 与 s[i..] 的最长公共前缀长度，Z[0]=n
Z-box 区间	[l,r] 表示已找到的最靠右的、与串首完全吻合的区间
min 的作用	Z[i] = min(r-i+1, Z[i-l]) 给出安全下界，情形二直接收敛
while 的边界	仅当匹配延伸到 r 之后才真正比较，情形三由此处理
线性的根源	r 只增不减，while 成功总次数不超过 n
哨兵拼接	pattern#text 使 Z 值不会跨边界，等于 m 即匹配
下标换算	拼接串位置 i 对应主串 i-m-1
LCS 的坑	无公共子串时 endPos 保持 0，直接截取会产生负下标

十一、拓展应用

Z 数组的用途远不止模式匹配，同一套预处理还能解决不少经典问题：

• 字符串周期检测：若 n 能被 n - Z[n-1] 整除且 Z[n-1] > 0，则最小周期为 n - Z[n-1]

• 统计本质不同子串、求每个前缀出现次数，可配合后缀数组互相印证

• 字符串压缩（如 ABCABABC 这类重复模式识别）与最短循环节判定

• 多模式匹配时可改用 Aho-Corasick 自动机，避免每个模式串重复建串

• 把哨兵字符换成不可能出现在输入中的字符，或改用整型数组预处理，彻底规避字符集冲突