Eternity

Until The End

Z函数（扩展Kmp）

发表于 更新于 分类于 ，
本文字数： 3.4k 阅读时长 ≈ 3 分钟

“$\text{Plan Z never fail!}$”

Z 函数

对于一个长度为 $len$ 的字符串 $s$ ，有一个长度为 $len$ 的数组称之为 $z$ ，其中 $z[i]$ 表示 $s[1..len]$ 与 $s[i..len]$ 的最长公共前缀 $LCP$ ，那么 $z$ 被称为 $s$ 的 $z$ 函数。

用文字叙述，即是 $z[i]$ 表示的是字符串 $s$ 与 $s$ 以 $i$ 开头的后缀字串的最长公共前缀长度。

一些需要了解的

在有些领域，有这样一个特殊定义 $z[1]=0$ ，即 $s[1..len]$ 与 $s[1..len]$ 的 $LCP$ 值为 $0$ 。但是，以普遍理性而言，这个定义是赘余的，但是，对于国际上现在通用的求 $z[]$ 的办法，对于求 $z[i]$ ，我们需要使用到 $z[0..i-1]$ 。而其中，所需要的，即是 $z[0]=0$ 。但是，在洛谷上的模板题，需要记入的答案是 $z[1]=length(s)$ 。那么，挺玄学的。

暴力求解

时间复杂度 $O(n^2)$ 。当然就是每一个后缀都一一比较即可。

线性时间求解

这个算法，国外称之为 $Z\ Algorithm$ ，国内则更偏向于 $Kmp.Ex$ 。原因在于此算法的做法和用处都与 $Kmp$ 相类似。

我们给出一个新的定义称为 Z-box ，对于一个 $i$ 而言，我们将区间 $[i,i+z[i]-1]$ 称为是 $i$ 的匹配段，即 Z-box 。

在求解 Z 函数时，我们需要维护右端点最右值的匹配段。为了方便，记作区间 $[l,r]$ 。因为区间 $[l,r]$ 是匹配段，那么， $s[l..r]$ 肯定是 $s$ 的前缀子串。在计算 $z[i]$ 时，我们需要保证 $l\le i$ 。且初始时， $l=r=0$ 。

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

  • 如果 $i\le r$ ，那么根据 $[l,r]$ 的定义有 $s[i,r]=s[i-l,r-l]$ ，因此 $\min(z[i-l+1],r-i+1)\leq z[i]$ 。这时：

    1. 若 $z[i-l]\leq r-i+1$ ，则 $z[i]=z[i-l]$ 。
    2. 否则 $z[i-l]\geq 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$ 即可。

复杂度分析

内层函数满足将 $r$ 向后移，而 $r<n-1$ ，共执行 $n$ 次。外层线性遍历，同样是 $n$ 次，总时间复杂度 $\mathcal O(n)$ 。

应用

详见 OI Wiki

洛谷模板题 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<iomanip>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#define gh() getchar()
#define re register
#define db double
typedef long long ll;
using namespace std;
const int MAXS=2e7+1;
template<class T>
inline void read(T &x)
{
    x=0;
    char ch=gh(),t=0;
    while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=gh();
    if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
template<class T>
inline bool checkMax(T &x,T &y)
{
    return x<y?x=y,1:0;
}
template<class T>
inline bool checkMin(T &x,T &y)
{
    return x>y?x=y,1:0;
}
char Str_a[MAXS],Str_b[MAXS];
int Z[MAXS],P[MAXS],Len_a,Len_b;
ll ans;
inline void getZ_Func(char *s,int *z)
{
    int len=strlen(s+1); 
    for(re int i=1;i<=len;++i) z[i]=0;
    Z[1]=len;   //特殊判定
    for(re int i=2,l=0,r=0;i<=len;++i)
    {
        if(i<=r&&z[i-l+1]<r-i+1) z[i]=z[i-l+1];
        else
        {
            z[i]=max(0,r-i+1);
            while(i+z[i]<=len&&s[z[i]+1]==s[i+z[i]]) ++z[i];
        }
        if(i+z[i]-1>r) l=i,r=i+z[i]-1;
    }
    return ;
}       //自匹配
inline void ex_Kmp(char *s1,int *z,char *s2,int *p)
{
    getZ_Func(s2,z);
    int len=strlen(s1+1);
    for(re int i=1;i<=len;++i) p[i]=0;
    for(re int i=1,l=0,r=0;i<=len;++i)
    {
        if(i<=r&&z[i-l+1]<r-i+1) p[i]=z[i-l+1];
        else 
        {
            p[i]=max(0,r-i+1);
            while(i+p[i]<=len&&s1[i+p[i]]==s2[p[i]+1]) ++p[i];
        } 
        if(i+p[i]-1>r) l=i,r=i+p[i]-1;
    }
    return ;
}       //模式串匹配
int main()
{
    // freopen("Kmp-Ex.in","r",stdin);
    // freopen("Kmp-Ex.out","w",stdout);
    scanf("%s%s",Str_a+1,Str_b+1);
    Len_a=strlen(Str_a+1),Len_b=strlen(Str_b+1);
    getZ_Func(Str_b,Z);
    for(re int i=1;i<=Len_b;++i) ans^=1ll*i*(Z[i]+1);
    printf("%lld\n",ans);
    ex_Kmp(Str_a,Z,Str_b,P);
    ans=0;
    for(re int i=1;i<=Len_a;++i) ans^=1ll*i*(P[i]+1);
    printf("%lld",ans);
    return 0;
}
/*
aaaabaa
aaaaa
*/
相关文章