fccc
搜索文章Ctrl+K

Appearance

z函数

z函数 ​

z函数是一种字符串算法，它在国内还有个名字是扩展kmp，如果理解了Manacher算法，那么z函数理解起来会简单很多，求出z数组的过程和Manacher算法很像

首先我们约定字符串下标是以0为起点

一、定义 ​

对于一个长度为n的字符串s，我们定义一个函数z[i]，表示字符串s与s的后缀s[i,…,n−1]（以i为起点的后缀）的最长公共前缀（LCP） 的长度

z[i]=max(k|s[0,…,k−1]=s[i,…,i+k−1])

特别的，在z函数中z[0]是用不到的，约定z[0]=0，初始是从1开始求的

例如：字符串s为aaabaac，那么他的子函数的值如下

下标0123456
saaabaac
z0210210

接下来就是如果快速求出z数组，求解过程和Manacher算法很像

z函数的核心原理 ​

1.匹配右边界r ​

注意： r为扩展区域的开区间右边界

r是从某个位置开始的后缀与s所匹配的右边界的最大位置，与Manacher算法类似，只有突破比当前r更靠后的位置时才更新r

text
比如字符串s为aaabaac
初始r=0，i=1
i=1 z[1]=2，右边界为i+z[i]=3>r，r更新成3
i=2 z[2]=1，右边界为i+z[2]=3==r，不需要更新
i=3同理无需更新
i=4 z[4]=2，右边界为i+z[4]=6>r,所以r更新成6

2.匹配中心c ​

还是与Manacher算法很像，匹配右边界r对应的第一次起始下标i,则c就等于i
例如s=aaabaac，第一次r更新成3，是i=1，c也同步更新c=i，第二次为i=4时，r突破更新成6，c同步更新成c=i=4

3.z函数的过程 ​

当来到出发点i，利用z,r,c对过程进行加速，主要分为两大类共4种情况

a.i没有被r包住，可以直接暴力往后扩 ​

b.i被r包住，关键点i-c的扩展长度，对于大扩展区域以内i+z[i-c]<r，直接确定z[i]=z[i−c] ​

text
这是在大扩展区域以内
例如z[15]=8 z[3]=4 此时r=22,c=15
s:15 16 17 18 19 20 21 22 | 23
s:0  1  2  3  4  5  6  7  | 8    s[8]!=s[23]

s:3 4 5 6 | 7
s:0 1 2 3 | 4  s[4]!=s[7]

如果我们计算z[18] i=18 关键点i-c=3
有上面两段对应关系s[18,...,22]=s[3,...,7]  s[3,...,6]=s[0,...,3] 
于是就得到s[18,...,21]=s[0,...3] 且s[22]=s[7]!=s[4]
所以当i+z[i-c]<r时，可以直接确定z[i]=z[i-c]

c.i被r包住，关键点i-c的扩展长度，对于大扩展区域以外i+z[i-c]>=r，直接确定z[i]=r−i ​

text
如果关键点超过去了
例如z[15]=6 z[3]=5 此时r=21,c=15
s:15 16 17 18 19 20 | 21
s:0  1  2  3  4  5  | 6     s[6]!=s[21]

s:3 4 5 6 7 | 8
s:0 1 2 3 4 | 5   s[5]!=s[8]

还是求z[18] 
根据b我们容易确定z[18,19,20]=z[0,1,2]
由于s[6]!=s[21]而且s[6]=3导致s[21]必然不等于s[3]
所以z[i]=r-i

和Manacher算法一样，b和c两点，哪个长度短哪个就是z[i]

d.i被r包住，关键点i-c的扩展长度，对于大扩展区域的边界i+z[i-c]==r-1，从边界r开始往外扩 ​

text
如果在大扩展区域边界上，此时无法根据边界点直接确定
z[15]=6 z[3]=3 r=21 c=15
s:15 16 17 18 19 20 | 21
s:0  1  2  3  4  5  | 6     s[6]!=s[21]

s:3 4 5 | 6 
s:0 1 2 | 3    s[3]!=s[6]

还是求z[18] 我们能够确定z[18..20]=z[0..2]
z[21]!=z[6],z[6]!=z[3]不能得出z[21]!=z[3]
因此需要从边界开始往外暴力扩

从为了代码简单，可以讲c和d情况合并，从边界开始扩展，代码量会更少

时间复杂度分析 ​

时间复杂度： O(n)。右端点 r 单调递增，最高增加到 n−1。每次暴力比较失败时算法立即停留在该位置，后续 r 会右移，故字符比较的总次数不超过 2n

z函数模板 ​

z函数模板
c++
std::vector<int> zArray(const std::string& s) {
    int n = s.size();
    std::vector<int> z(n, 0);
    for (int i = 1, c = 0, r = 0; i < n; ++i) {
        int len = (r > i) ? std::min(r - i, z[i - c]) : 0;
        while (i + len < n && s[i + len] == s[len]) ++len;
        if (i + len > r) {
            r = i + len;
            c = i;
        }
        z[i] = len;
    }
    return z;
}

e数组 ​

给定两个字符串a和b，e[i] 表示后缀 a[i…n−1] 与前缀 b[0…m−1] 的最长公共前缀（LCP）长度。

需要求出字符串b的z函数，然后求e数组与z函数差不多

注意： e数组是要从下标为0开始求

e函数模板 ​

e数组模板
c++
std::vector<int> eArray(const std::string& a, const std::string& b, const std::vector<int>& z) {
    int n = a.size(), m = b.size();
    std::vector<int> e(n, 0);
    for (int i = 0, c = 0, r = 0; i < n; ++i) {
        int len = (r > i) ? std::min(r - i, z[i - c]) : 0;
        while (i + len < n && len < m && a[i + len] == b[len]) ++len;
        if (i + len > r) {
            r = i + len;
            c = i;
        }
        e[i] = len;
    }
    return e;
}