luoguP5410 【模板】扩展 KMP（Z 函数）

新学一发扩展 KMP.

和 KMP 一样，都是均摊复杂度 $O(n)$.

code:

#include <bits/stdc++.h>        
#define N 20000007    
#define ll long long  
#define setI(s) freopen(s".in","r",stdin) 
#define setO(s) freopen(s".out","w",stdout) 
using namespace std;    
int z[N],p[N];                
char a[N],b[N];        
void Z(char *s,int len) 
{
    for(int i=1;i<=len;++i) z[i]=0;    
    z[1]=len;    
    for(int i=2,l=0,r=0;i<=len;++i) 
    {
        if(i<=r) z[i]=min(z[i-l+1],r-i+1);    
        for(;i+z[i]<=len&&s[i+z[i]]==s[z[i]+1];++z[i]);   
        if(i+z[i]-1>r) l=i,r=i+z[i]-1;     
    }
}     
void exkmp(char *s,int n,char *t,int m) 
{
    Z(t,m);      
    for(int i=1;i<=n;++i) p[i]=0;    
    for(int i=1,l=0,r=0;i<=n;++i) 
    {
        if(i<=r) p[i]=min(z[i-l+1],r-i+1);      
        for(;i+p[i]<=n&&s[i+p[i]]==t[p[i]+1];++p[i]);           
        if(i+p[i]-1>r) l=i,r=i+p[i]-1;   
    }
}
int main() 
{ 
    // setI("input");           
    int n,m; 
    scanf("%s",a+1),n=strlen(a+1);   
    scanf("%s",b+1),m=strlen(b+1);              
    exkmp(a,n,b,m);    
    ll ans=0;   
    for(int i=1;i<=m;++i) ans^=1ll*i*(z[i]+1);    
    printf("%lld\n",ans);   
    ans=0;    
    for(int i=1;i<=n;++i) ans^=1ll*i*(p[i]+1);    
    printf("%lld\n",ans);   
    return 0;  
}