Z 函数

介绍

Z 函数是字符串算法中的一个重要函数，对于一个字符串 \(s\) 而言，\(z[i]\) 描述了以 \(s[i]\) 开始的后缀与 \(s\) 的最长公共前缀。

在此约定 \(z[0] = 0\) 。

示例：对于字符串 aabaabc 而言，其 Z 函数为：\(\{ 0, 1, 0, 3, 1, 0, 0 \}\) 。

Z 函数有很多应用，比如字符串匹配等，等会我们会一一介绍。

线性时间复杂度计算 Z 函数

假设要计算 \(s\) 的 Z 函数，考虑对于任意 \(i \in [0, |s| - 1]\) ，都计算后缀 \(s[i :]\) 和 \(s\) 的最长公共前缀，则时间复杂度为 \(O(|s| ^ 2)\) 。

所以在这里我们给出一种线性计算 Z 函数的方法：

我们在这里使用两个变量：\(l\) 和 \(r\) ，初始化均为 0，\(r\) 维护当前已经计算过的最大的 \(i + z[i] - 1\) ，即目前计算的过的 \(s[i :]\) 公共前缀最长延续的下标，\(l\) 则表示取最大值时 \(i\) 的索引，即 \(r = l + z[l] - 1\) 。

接下来从 1 开始便利字符串下标 \(i\) 即可：

1. 若 \(i \leq r\) ：

   根据定义有 \(s[i : r] = s[i - l : r - l]\) ，因此：

   • 若 \(z[i - l] < r - i + 1\) ，则 \(z[i] = z[i - l]\) ；
   • 若 \(z[i - l] \geq r - i + 1\) ，则 \(z[i] = r - i + 1\) ，然后按照 Z 函数的定义继续扩展。

2. 若 \(i > r\) ：

   我们只需令 \(z[i] = 0\) ，然后按照 Z 函数的定义继续拓展即可。

每一轮循环结束后对 \(l\) 和 \(r\) 进行更新。

代码实现：

std::vector<int> z_function(const std::string& pat) {
    int n = pat.size();
    std::vector<int> z(n);
    for (int i = 1, l = 0, r = 0; i < n; i++) {
        if (i <= r && z[i - l] < r - i + 1) {
            z[i] = z[i - l];
        }
        else {
            z[i] = std::max(0, r - i + 1);
            while (i + z[i] < n && pat[z[i]] == pat[i + z[i]]) z[i]++;
        }
        if (i + z[i] - 1 > r) {
            l = i;
            r = i + z[i] - 1;
        }
    }

    return z;
}

注意到，内层 while 循环每一轮都会使得 r 加 1，而外层循环只有一次遍历，因此时间复杂度为 \(O(n)\) 。

Z 函数的应用

线性时间复杂度匹配子串

众所周知，KMP 算法可以实现线性时间复杂度内查找字符串 \(s\) 中是否存在子串 \(p\) ，使用 Z 函数则可以更为简洁地实现同样的效果：

我们构造一个新字符串 \(sp = p + \Delta + s\) ，\(\Delta\) 表示一个分割字符，其不在 \(p\) 和 \(s\) 中出现，接下来计算 \(sp\) 的 Z 函数，若 \(sp\) 的 Z 函数存在某个值等于 \(|p|\) ，则说明 \(p\) 是 \(s\) 的子串，反之则说明不是。

示例代码（ haystack 为文本串，needle 为模式串）：

时间复杂度：\(O(|s| + |p|)\)

class Solution {
public:
    int strStr(std::string& haystack, std::string& needle) {
        std::string str = needle + '&' + haystack;
        int n = str.size(), p = needle.size();
        std::vector<int> z(n);
        for (int i = 1, l = 0, r = 0; i < n; i++) {
            if (i <= r && z[i - l] < r - i + 1) {
                z[i] = z[i - l];
            }
            else {
                z[i] = std::max(0, r - i + 1);
                while (i + z[i] < n && str[z[i]] == str[i + z[i]]) z[i]++;
            }
            if (z[i] == p) return i - p - 1;
            if (i + z[i] - 1 > r) {
                l = i;
                r = i + z[i] - 1;
            }
        }

        return -1;
    }
};