题解 P5410 【【模板】扩展 KMP】
cosmicAC
2019-05-22 09:52:57
**本文不会介绍Z算法的复杂度证明** ~~(因为我也不会证)~~。
大家的Z算法都好长啊，还分成了两个部分。其实是可以统一处理的，`extend`和`nxt`可以开成同一个`z`数组（毕竟代码也一模一样），表示第i个后缀和原串的LCP。
就算写在了一起还是觉得代码好长啊，所以稍微魔改一下，就变的和manacher算法一模一样了。（其实思想也是一样的）
关键有效代码只有三行，注意**从0开始标号**：
```cpp
for(int i=1,mx=0,l=0;s[i];i++){
z[i]=i<mx?std::min(mx-i,z[i-l]):0; //1
while(s[z[i]]==s[i+z[i]])z[i]++; //2
if(i+z[i]>mx)mx=i+z[i],l=i; //3
}
```
`mx`就是当前能覆盖到最远的位置，`l`就是`mx`所对应的起始点(即`mx=l+z[l]`)。
第一行的意思是，如果当前的位置`i`已经能够被之前的`z`值覆盖了，就可以把问题规约到`z[i-l]`。因为根据`z`的定义，第`l`位和第0位的LCP包含了`i`，所以第`i`位和第`i-l`位是“差不多”的，`z`值自然也是差不多。当然也要和`mx-i`取一下min，因为这个“差不多”延伸显然不能超过`mx-i`。
第二行没什么意思，就是像manacher一样暴力匹配。
第三行就是更新右端点。
我相信会manacher的人都懂了。
再回到本题，题目里要求的是b与a的每一个后缀的LCP，容易发现，把两个串加个分隔符接在一起即可。输出就是除了分隔符之外的z数组原样输出。
超短的完整代码如下
```cpp
#include<bits/stdc++.h>
int m,z[1<<21];char s1[1<<20],s[1<<21];
int main(){
scanf("%s%s",s1,s);m=strlen(s);
strcat(s,"#"),strcat(s,s1);
for(int i=1,mx=0,l=0;s[i];i++){
z[i]=i<mx?std::min(mx-i,z[i-l]):0;
while(s[z[i]]==s[i+z[i]])z[i]++;
if(i+z[i]>mx)mx=i+z[i],l=i;
}
for(int i=0;i<m;i++)printf("%d ",i?z[i]:m); //题面里钦定z[0]=m
puts("");
for(int i=m+1;s[i];i++)printf("%d ",z[i]);
return 0;
}
```
另外，这个东西也是可以做[P3375](https://www.luogu.org/problemnew/show/P3375)的。利用manacher的思想，在mx更新的时候顺便维护原版KMP的nxt数组即可。
就是下面这样：
```cpp
if(i+z[i]>mx){
for(int j=mx;j<i+z[i];j++)nxt[j]=j-i+1;
mx=i+z[i],l=i;
}
```