Z函数

Z函数\(Z_i\)表示了在一个字符串\(S\)中,由第\(i\)个字符开始的后缀和整个串的最长公共前缀的长度。
至于\(Z_0\)的值其实没有意义,可以设成\(0\)或是\(n\)。下文令\(Z_0=0\)。

下文中的下标都从零开始。


朴素做法

很容易,我们可以找到一个朴素算法,它以最简单的方法,对于每一个位置\(i\)手动检查最大的\(Z_i\):

void zfunc(string str, int n, int* z) {
    z[0] = 0;
    FOR (i, 1, n-1) {
        z[i] = 0;
        while (i+z[i] < n && str[i+z[i]] == str[z[i]])
            z[i]++;
    }
}

很显然,这个算法有时(比如\(S=\text{“}\underbrace{\text{aaaaaaaaaa}}_{n}\text{”}\))会退化到\(O(n^2)\)。

Z算法

我们考虑在计算后面的值时重复使用之前计算好的值。维护一个区间\([l,r]\),表示之前计算过的所有由\([i,i+Z_i-1]\)覆盖过的区间中最靠右的。来看下面的例子:

\[\large\underbrace{\overbrace{\text{abc}}^{[0,\text{len}]}\overbrace{\text{abc}}^{[i-l,\text{len}]}}_{[0,r-l]}\color{Blue}\text{abc}\color{Black}\text{qaq}\underbrace{\text{abc}\overbrace{\text{abc}}^{[i,\text{len}]}}_{[l,r]}\color{Red}\text{xyz}\]

我们接下来要计算\(Z_i\)的值。我们考虑在朴素计算之前,先使用当前这个区间为\(Z_i\)赋一个初值:

由于\(S[0,r-l]=S[l,r]\),其中\(S[l,r]\)表示从\(S_l\)开始到\(S_r\)结束的子串,我们有

\[S[i,\text{len}=\min(Z_{i-l},r-i+1)]=S[i-l,\text{len}=\min(Z_{i-l},r-i+1)]=S[0,\text{len}=\min(Z_{i-l},r-i+1)]\]

其中\(S[i,\text{len}=l]\)表示从\(S[i]\)开始,长为\(l\)的子串。解释一下这个式子:

  • \(i-l\)是前缀\(S[0,r-l]\)中\(i\)出现的位置。
  • 为了防止在我们尚不了解的超出\([l,r]\)的位置出现差错(红色部分),我们需要把\(Z_{i-l}\)和\(i\)到\(r\)距离\(r-i+1\)取最小值。

然后再使用朴素做法尝试增加\(Z_i\)的值。

void zfunc(string str, int n, int* z) {
    z[0] = 0;
    int l, r;
    l = r = 0;
    FOR (i, 1, n-1) {
        if(i <= r)
            z[i] = min(r-i+1, z[i-l]);
        else
            z[i] = 0;
        while (i+z[i] < n && str[i+z[i]] == str[z[i]])    // 朴素部分
            z[i]++;
        if(r < i+z[i]-1) {
            l = i;
            r = i+z[i]-1;
        }
    }
}
时间复杂度

使\(Z_i\)增加的基本操作是形如str[i+z[i]] == str[z[i]]的判断。我们称判断为真的为有效判断,为假的为无效判断。只有有效判断会使当前的\(Z_i\)增加。容易看出:

  • 对于每一个\(i\),最多进行一次无效判断。总共最多进行\(n\)次无效判断。
  • 所有有效判断的右端(\(S_{i+Z_i}\))一定在当前的\([l,r]\)区间外,且在右侧。这可能需要思考一下:如果有效判断在内侧,则前面的\(Z_{i-l}\)一定也可以增加。
    • 所以,每一次有效判断都会把\(r\)往右推一个单位,总共最多进行\(n\)次有效判断。

所以总体的复杂度就是\(O(n)\)。

用途

其他的我不会……

字符串查找

只要把两个字符串中间放一个没出现过的字符,然后计算Z函数,就相当于求前面字符串和后面字符串的每一个后缀的最长公共前缀。这可以解决许多问题,比如字符串查找。

“Z函数”的一个回复

发表评论

电子邮件地址不会被公开。 必填项已用*标注