Z函数

发表于 更新于 分类于
  • 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$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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$

1
2
3
4
5
6
7
8
9
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;
}