title: “Z函数”
date: 2024-10-24 11:38:41
updated: 2024-12-27 08:25:31
tag: [“notion”, “Algorithm”, “数组字符串”]
categories: “Algorithm”
mathjax: true
comments: true
description: ‘

• Z函数

Z函数

对于一个长度为 $n$ 的字符串 $s$，定义函数 $z[i]$ 表示 $s$ 和 $s[i,n-1]$（即以 $s[i]$ 开头的后缀）的最长公共前缀（LCP）的长度，则 $z$ 被称为 $s$ 的 Z 函数。特别地，$z[0] = 0$。维护右端点最靠右的匹配段，记作$[l,r]$。

在计算$z[i]$的过程中：

• 如果$i\le r$，那么根据$[l,r]$的定义有$s[i,r]=s[i-l,r-l]$，因此$z[i]\ge min(z[i-l], r-i+1)$ 。这时：
  • 若$z[i-l]<r-i+1$，则$z[i]=z[i-l]$。
  • 否则$z[i-l]\ge r-i+1$，这时我们令$z[i]=r-i+1$，然后暴力枚举下一个字符扩展$z[i]$直到不能扩展为止。
• 如果$i>r$，那么我们直接按照朴素算法，从$s[i]$开始比较，暴力求出$z[i]$。
• 在求出$z[i]$后，如果$i+z[i]-1>r$，我们就需要更新 $[l,r]$，即令$l=i,r=i+z[i]-1$。

data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7

vector<int> z_func(const string& s) {
    int n = s.length();
    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] = max(0, r - i + 1);
            while (i + z[i] < n && s[z[i]] == s[i + z[i]]) ++z[i];
        }
        if (i + z[i] - 1 > r) l = i, r = i + z[i] - 1;
    }
    return z;
}

注意到在while (i + z[i] < n && s[z[i]] == s[i + z[i]]) ++z[i]; 之前z[i] 达到了$r$，所以每次++z[i] 才会增长$r$。$r=l+z[i]-1$，只用$l$一个变量就可以得到$r$，一旦触发循环则只需要更新一次$l$

vector<int> z_func(const string& s) {
    int n = s.size();
    vector<int> z(n);
    for (int i=1,l=0; i<n; i++) { // r = l+z[l]-1; 最右匹配点
        if (i<l+z[l]) z[i] = min(z[i-l], l+z[l]-i);
        while (i+z[i]<n && s[z[i]] == s[i+z[i]]) ++z[l=i];
    }
    return z;
}