(color{#A4A4A4}{谢谢好哥哥帮我写的markdown，哭了})
(exkmp)，也称(z−algorithm)
是用来求一个字符串的每个后缀与原串的LCP，即字符串中后缀=前缀的长度。
z[i]表示以第i位为开头的后缀与前缀相等的最大长度。
例如字符串ababaa，可求出它的z函数为603011。
这个函数的求法有点类似于(manacher)。
首先，特别规定z[1]=字符串长度。
接下来从第二位枚举。设i为当前枚举到的字符串位数。
设 (l) 表示当前区间右端点最靠右的后缀的首位（左端点），即i+z[i]最大的i；
设 (r) 表示该区间的右端点，即i+z[i]−1。
对于当前的(i)，若有(i<=r)，即(i)被(l)的区间包括了，
即区间((i,r)=)区间((i−l+1,r−l+1))。（都是闭区间）
所以，第(i)位与第(i−l+1)位相同，有(z[i]=z[i−l+1])；
但这段区间也不能超过(r−l+1)，所以(z[i]<=r−i+1)。
综上所述，z[i]=min(z[i−l+1],r−i+1)。
后面的部分只要一位一位暴力枚举比较即可；
当(i>r)时，也用暴力枚举求出。
最后不要忘了更新(l、r)。
对于这道题的第二问（b与a的每一个后缀的LCP长度），需在第一问的基础上求出。
只需要被比较的函数不变，用来比较的函数换成a即可。
设a的第i位开始的与b的LCP为p[i]
注意，在操作p[i]=min(z[i−l+1],r−i+1)时，不要把后面的z[i−l+1]写成p[i−l+1]（因为与自身相同的不是a字符串）。
注意这道题不要忘记longlong！（包括后面的1ll）
代码如下 吸氧过的…
#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#define MogeKo qwq
using namespace std;
const int maxn = 2e7+10;
char a[maxn],b[maxn];
int len1,len2,z[maxn],p[maxn];
long long ans;
void get_z(char *s,int n) {
z[1] = n;
int l = 0,r = 0;
for(int i = 2; i <= n; i++) {
if(i <= r) z[i] = min(z[i-l+1],r-i+1);
while(i+z[i] <= n && s[i+z[i]] == s[1+z[i]]) z[i]++;
if(i+z[i]-1 > r) l = i, r = i+z[i]-1;
}
}
void exkmp(char *s,char *t,int n) {
int l = 0,r = 0;
for(int i = 1; i <= n; i++) {
if(i <= r) p[i] = min(z[i-l+1],r-i+1);
while(i+p[i] <= n && s[i+p[i]] == t[1+p[i]]) p[i]++;
if(i+p[i]-1 > r) l = i, r = i+p[i]-1;
}
}
int main() {
scanf("%s%s",a+1,b+1);
len1 = strlen(a+1),len2 = strlen(b+1);
get_z(b,len2);
for(int i = 1; i <= len2; i++)
ans ^= 1ll*i*(z[i]+1);
printf("%lld
",ans);
ans = 0;
exkmp(a,b,len1);
for(int i = 1; i <= len1; i++)
ans ^= 1ll*i*(p[i]+1);
printf("%lld
",ans);
return 0;
}