题解 P5410 【【模板】扩展 KMP】

· · 题解

本文不会介绍Z算法的复杂度证明 (因为我也不会证)。

大家的Z算法都好长啊，还分成了两个部分。其实是可以统一处理的，extend和nxt可以开成同一个z数组（毕竟代码也一模一样），表示第i个后缀和原串的LCP。

就算写在了一起还是觉得代码好长啊，所以稍微魔改一下，就变的和manacher算法一模一样了。（其实思想也是一样的）

关键有效代码只有三行，注意从0开始标号：

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数组原样输出。

超短的完整代码如下

#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的。利用manacher的思想，在mx更新的时候顺便维护原版KMP的nxt数组即可。

就是下面这样：

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;
}