• 周六. 10月 8th, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

前缀函数与Z函数

admin

11月 28, 2021

字符串算法果然玄学=_=
参考资料:
OI Wiki:前缀函数与KMP算法
OI Wiki:Z函数(扩展KMP)

0. 约定

字符串的下标从 (0) 开始。
对于长度为 (n) 的字符串 (s),记其每一个字符分别为 (s_0, s_1, cdots, s_{n-1})
子串 (s_l, s_{l+1}, cdots, s_{r-1}, s_r) 简记为 (s(l,r))
对于字符串 (a, b)(a+b) 表示拼接操作,即将字符串 (b) 拼接到字符串 (a) 之后,构成新的字符串。
记构成的新字符串为 (c),则上述拼接操作记为 (cgets a+b)
不论是字符还是字符串,皆不加引号。

1. 前缀函数

1. 前缀函数的定义

对于字符串 (s),若存在一个非本身的子串 (t) 使得 (t) 既是 (s) 的前缀又是 (s) 的后缀,称 (t)(s) 的一个 ( ext{Border})
更加符号化地,对于一个长为 (n) 的字符串 (s),若存在 (m) 使得 (s
eq m)
(s(0,m-1)=s(n-m+1,n))
(s(0,m-1)) ((s(n-m+1,n)) 同理) 为 (s) 的一个长度为 (m)( ext{Border})
对于一个字符串 (s),定义 ( ext{MaxBorder}(s))(s)( ext{Border}) 中最长的。
接下来定义前缀函数:
对于一个字符串 (s),定义前缀函数 (pi(s,i))( ext{MaxBorder}(s(0,i))) 的长度。
在不引起歧义的情况下,可简记为 (pi(i));特别地,定义 (pi(s,0)=0)
有时我们关心一整个字符串的长度,故此时我们也可以记 (pi(s)={pi(s,0), pi(s,1), cdots, pi(s,n-1)})

举一个实例:(pi( exttt{abacaba})={0,0,1,0,1,2,3})

2. 前缀函数的重要性质

显然直接根据定义计算前缀函数的时间复杂度是不能接受的,于是我们需要依赖一些有用的性质来加速计算。
主要的性质有下面两个:

  1. (pi(i+1)leqslantpi(i)+1),且仅当 (s_{pi(i)}=s_{i+1}) 时有 (pi(i+1)=pi(i)+1)
  2. (j)(s(0,i)) 中除 ( ext{MaxBorder}(s(0,i))) 外最长的 ( ext{Border}) 的长度,则 (j=pi(pi(i)-1))

第一个性质是显然的。第二个性质由 (s(0,j-1)=s(i-j+1,i)=s(pi(i)-j,pi(i)-1)) 自然导出。

3. 快速求前缀函数

这样我们就有了快速求前缀函数的算法:
我们从前向后迭代求。假设我们已经求出了 (pi(0), pi(1), cdots, pi(i-1)),现在要求 (pi(i))
(j=pi(i-1))。如果 (s_i=s_j),则 (pi(i)=j+1)
否则,令 (jgets pi(j-1)),重复以上判断直到满足 (s_i=s_j)(j=0)
(j=0),则 (pi(i)=0)

如此重复直到前缀函数全部计算完成。可以证明,时间复杂度为 (O(n))

code:

void prefix()
{
    for(int i=1;i<=n-1;i++)
    {
        int j=pi[i-1];
        while(j>0&&s[i]!=s[j])j=pi[j-1];
        if(s[i]==s[j])j++;
        pi[i]=j;
    }
}

2. KMP

一般的方法是通过 (pi(i)) 优化匹配,不过有个简单粗暴地多的方法。
假设模式串为 (s),文本串为 (t)(s) 的长度为 (n)(t) 的长度为 (m)
构造字符串 (agets s+#+t),其中 (#)(s,t) 中均不会出现的字符。
然后求 (a) 的前缀函数,若(pi(a,i)=n),则 (s)(t)(i-2n) 处出现。
总时间复杂度 (O(n+m))。代码略。
优化:注意到前缀函数是可以一个一个字符在线处理的,所以空间复杂度可优化到 (O(n))

3. Z函数

定义 ( ext{lcp}(a,b)) 为字符串 (a, b) 的最长公共前缀。
定义Z函数:
对于一个长度为 (n) 的字符串 (s),定义Z函数 (z(s,i))( ext{lcp}(s,s(i,n-1))) 的长度。
在不引起歧义的情况下,可简记为 (z(i));特别地,定义 (z(s,0)=0)
有时我们关心一整个字符串的长度,故此时我们也可以记 (z(s)={z(s,0), z(s,1), cdots, z(s,n-1)})

举一个实例:(z( exttt{abacaba})={0,0,1,0,3,0,1})

发表回复

您的电子邮箱地址不会被公开。