Z 函数与后缀数组入门：从前缀匹配到全局子串关系

我最开始接触“Z 函数与后缀数组入门：从前缀匹配到全局子串关系”时，先遇到的是这个问题：Z 函数和后缀数组刚接触时都像一堆下标技巧，我花了不少时间才把“前缀匹配”和“后缀排序”对应到真实查询。我没有继续硬记结论，而是把过程画出来，再用一两个最小例子亲手跑通。这篇留下的，就是那次重新梳理后真正帮我想明白的东西。

Z 函数和后缀数组都属于字符串进阶结构。它们不像 KMP 那么常用，但能帮助我们理解“字符串和自身前缀的关系”以及“所有后缀之间的关系”。

Z 函数是什么

对字符串 s，z[i] 表示从位置 i 开始的后缀与整个字符串前缀的最长公共前缀长度。

s = a a b a a b a
z = 0 1 0 4 1 0 1

它可以用来做模式匹配。把 pattern + '#' + text 拼起来，如果某个位置的 Z 值等于模式串长度，就说明匹配成功。

Z 函数代码

int[] zFunction(String s) {
    int n = s.length();
    int[] z = new int[n];
    int left = 0, right = 0;
    for (int i = 1; i < n; i++) {
        if (i <= right) {
            z[i] = Math.min(right - i + 1, z[i - left]);
        }
        while (i + z[i] < n && s.charAt(z[i]) == s.charAt(i + z[i])) {
            z[i]++;
        }
        if (i + z[i] - 1 > right) {
            left = i;
            right = i + z[i] - 1;
        }
    }
    return z;
}

这里 [left, right] 表示当前已知的、与前缀匹配的一段最右区间。

后缀数组是什么

后缀数组把字符串的所有后缀按字典序排序。

s = banana

后缀：
0 banana
1 anana
2 nana
3 ana
4 na
5 a

排序后：
5 a
3 ana
1 anana
0 banana
4 na
2 nana

后缀数组常和 LCP 数组一起使用。LCP 表示排序后相邻后缀的最长公共前缀。

后缀数组适合什么问题

字符串哈希和后缀数组怎么选

字符串哈希实现简单，适合快速判断子串相等；但哈希存在冲突风险。后缀数组更系统，适合做全局子串关系分析，但实现和理解成本更高。

工程中，如果是普通业务匹配，往往不会手写后缀数组；如果是算法学习、文本分析、DNA 序列这类需求，后缀结构会更有价值。

我的分析

Z 函数像 KMP 的兄弟，重点在“当前后缀和前缀能匹配多长”。后缀数组则更像字符串的全局索引，把所有后缀统一排序后，很多子串问题就变成相邻比较。

这篇不要求一口气手写完整后缀数组倍增算法，先理解它解决什么问题更重要。

面试题

1. Z 函数和 KMP 都能匹配字符串，它们的视角有什么不同？
2. 后缀数组为什么能解决最长重复子串？
3. LCP 数组表示什么？
4. 字符串哈希和后缀数组各有什么优缺点？
5. 为什么后缀数组常用于全局子串关系问题？