题目链接

P5410 【模板】扩展 KMP（Z 函数） - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

分析

先考虑 z 数组

设 nx[i] 为字符串 b 与 b 以 b[i] 开头的后缀最长公共前缀

设 i为当前需要求的位置

当前 i+nx[i]-1 的最大值所对应的 i 为 q 

p 为 i 对应的位置

当 i 大于 q+nx[q]-1时

暴力扩展即可

当 i 小于 q+nx[q]-1 时

如图

那么 p~nx[q] 与 i~q+nx[q]-1 是相同的

q+nx[q]与 nx[q]+1 （即 q 扩展的下一个位置）是不同的

当 p+nx[p]-1 小于 nx[q] 时

如图

nx[i]=nx[p]

当 p+nx[p]-1 大于 nx[q] 时

如图

nx[i]=q+nx[q]-i

当 p+nx[p] 等于 nx[q] 时

nx[i] 大于或等于 q+nx[q]-i

令其等于 q+nx[q]-i 再暴力扩展即可

再考虑 p 数组

我们发现与 z 数组求法相同

只是 p 从原字符串变到另一字符串而已

细节

22pts：需要开 long long

93pts：求 p 数组扩展时 ex[i]+1 不能超过 b 数组长度

代码

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 
 4 #define int long long//细节1 
 5 
 6 const int N=20000007;
 7 
 8 char a[N],b[N];
 9 
10 int nx[N],ex[N];
11 
12 signed main(){
13     scanf("%s %s", a+1, b+1);
14     int la=strlen(a+1),lb=strlen(b+1);
15     nx[1]=lb;
16     int ans=lb+1;
17     for(int i=2,q=0;i<=lb;i++){//z数组 
18         if(i<=q+nx[q]-1){
19             int p=i-q+1;
20             if(p+nx[p]-1<nx[q]) nx[i]=nx[p];
21             else nx[i]=q+nx[q]-i;//小于和等于赋值相同 
22         }
23         while(b[nx[i]+1]==b[i+nx[i]]) nx[i]++;//暴力扩展 
24         if(i+nx[i]-1>q+nx[q]-1) q=i;//更新q 
25         ans^=i*(nx[i]+1);//计算答案 
26     }
27     cout<<ans<<endl;
28     
29     ans=0;
30     for(int i=1,q=0;i<=la;i++){//p数组 
31         if(i<=q+ex[q]-1){
32             int p=i-q+1;
33             if(p+nx[p]-1<ex[q]) ex[i]=nx[p];
34             else ex[i]=q+ex[q]-i;
35         }
36         while(b[ex[i]+1]==a[i+ex[i]]&&ex[i]+1<=lb) ex[i]++;//细节2 
37         if(i+ex[i]-1>q+ex[q]-1) q=i;
38         ans^=i*(ex[i]+1);
39     }
40     cout<<ans<<endl;
41     return 0;
42 }