Z 函数（扩展 KMP）
定义
-
我们约定字符串下标从
0 开始。 -
对于字符串
s （len=n ），定义z_i 为s_{i\sim n-1} （即以i 为起点的后缀）与s 的最长公共前缀长度。
实现原理
-
首先我们肯定会一个
O(n^2) 暴力：枚举i ，从i 向后逐位比对。 -
考虑利用自动机思想。假如我们已经求出了
z_{0\sim i} ，如何快速地求z_{i+1} ？ -
定义
l,r 分别为对应匹配段（指从i 开始的后面那段）的左右端点。 -
我们定义
Z-box 为当前已经求出的所有匹配段中，r 最大的一段（下文的l,r 都是Z-box 的）。我们可以利用i 相对Z-bos 的位置来分类讨论快速求解。
-
当
i\leqslant r ：- 由
z 函数定义，我们有s[0\dots z[l]-1]=s[l\dots r] （图中橙色部分）。 - 从而有
s[i-l\dots z[l]-1]=s[i\dots r] （图中灰色部分）。 - 又有
s[0\dots z[i-l]-1]=s[i-l\dots i-l+z[i-l]-1] （图中左侧的两个紫色部分）。 - 联立灰色部分和左侧的两个紫色部分，我们可以看出，
s[0\dots z[i-l]-1]=s[i\dots i+z[i-l]-1] ！ - 相应的会有紫色部分超出灰色部分的情况，这时我们就只能保证
z[i]\geqslant r-i+1 。 - 综合一下即为
z[i]\geqslant \min(z[i-l],r-i+1) 。更向后延伸的部分直接暴力匹配。
- 由
-
当
i>r ，纯暴力匹配。 -
每次处理完之后更新
Z-box 。 -
容易看出，每次暴力处理至少会使
r+1 ，r\leqslant n ，从而暴力次数O(n) ，非暴力转移O(1) ，总复杂度O(n) 。
ll z[maxn];
il void Z(string &s){
ll l=0,r=0; z[0]=s.size();
ll to=s.size()-1;
For(i,1,to){
if(i<=r) z[i]=min(z[i-l],r-i+1);
while(i+z[i]<=to && s[i+z[i]]==s[z[i]]) ++z[i];
if(i+z[i]-1>r) r=i+z[i]-1,l=i;
}
return;
}- 讲一点细节：为什么不
l,r=-1 然后从0 开始。 - 那样的话
l=0,r=sz-1 。可以看到r 永远不会被更新，从而l 也是，于是非暴力部分是假的，结果就是这退化成了O(n^2) 暴力。
应用
-
查询模式串
P 在文本串T 中的所有出现位置。 -
一种思路是模仿隔壁
\pi 函数加个分隔符拼一块，容易看出对于z[i]=|p|(i>|p|) （下标从0 开始所以不+1 ）的所有i ，i 是文本串中一个恰为模式串的子串的起始位置。
- 当然更直接的是放弃拼接，先对
P 本身做z 函数，然后再对T 做基于P 的z 函数（其实和KMP 高度近似）。- 详细来讲的话，不妨看图。
- 对
T 维护一个Z-box ，到i 时，两段灰色全同，则当前的z2[i] 有下界为\min(z[i'],r-i+1) 。 - 然后两边对比进行暴力，只不过这里多了一个条件：
z2[i]\leqslant |p| 。 - 总复杂度同
KMP ，O(|p|+|t|) 。
ll z2[maxn];
il void sZ(string &P,string &T){
Z(P); z[0]=P.size();
ll l=-1,r=-1,to=T.size()-1,sz=P.size();
For(i,0,to){
if(i<=r) z2[i]=min(z[i-l],r-i+1);
while(i+z2[i]<=to && z2[i]<sz && T[i+z2[i]]==P[z2[i]]) ++z2[i];
if(i+z2[i]-1>r) r=i+z2[i]-1,l=i;
}
return;
}- 跟字符串周期性质联合的各种乱搞。
- 考虑一个长度为
n ，周期为k 的字符串。即，对于该字符串s ，有s_{ik\sim (i+1)k-1}=s_{(i+1)k\sim (i+2)k-1} 。 - 稍微做一点观察，我们能看出一下几个基本性质：
-
- 该字符串的最长
border （如果不知道是什么，参看"前缀函数与 KMP"）为s_{0\sim n-k-1}=s_{k\sim n-1} 。换句话说，除去最前或最后两个循环节后，余下的两个字符串仍然全同。
-
- 观察上图。我们试着找一点和
z 函数相关的性质。 - 如图，
z[3]=7 。从而我们可以循环地搞事：上红=下橙，下橙=上橙，上橙=下绿，下绿=上绿... - 形象地总结一下的话，就是当
z[i]\geqslant i ，能循环；至于能循环多远，不超出i+z[i] ，而且要视k 与z[i] 的关系。 - 具体来讲，显然
i 以前的是一整个循环节，总共循环（包括i 以前那次）\lfloor\dfrac{z[i]}{k}\rfloor+1 次。 - 而如果要求找到整个串的最小循环节，那显然就是在说找到最小的
i+z[i]=n(i\leqslant \lfloor\dfrac{n}{2}\rfloor) 处。 - 简单证一下：如果
i>\lfloor\dfrac{n}{2}\rfloor ，无疑地，如果能循环，循环节长度< \lfloor\dfrac{n}{2}\rfloor 。既然循环节长度< \lfloor\dfrac{n}{2}\rfloor ，必然有一个更靠前的i 使得i+z[i]=n(i\leqslant \lfloor\dfrac{n}{2}\rfloor) 。 - 啊我在写什么,..
- 考虑一个长度为
.