本文参考洛谷题解：https://www.luogu.com.cn/article/cq4b4e5f
侵删

前言

exkmp 和 kmp 要求的东西比较类似。
exkmp 可以求出 $a_{i...n}$ 和 $b$ 的最长公共前缀。
这玩意也称 z 函数。

算法流程

求解 nxt 数组

定义 $nx{t}_i$ 为 $|lcp(b_{i..n},b)|$，也就是 $s$ 每一段后缀和自身的最长公共前缀。
例如：

那这玩意怎么求呢?
假设 $nx{t}_{\mathrm{0...}x-1}$ 已经求出，考虑如何求 $nx{t}_x$
还记得 $Manacher$ 是怎么做的吗？你要找到最靠右的回文串，然后用它的信息求当前回文半径。
类似的，对于所有的 $1\le x<n$ 我们要求出 $i+nx{t}_i-1$ 的最大值，记最大值编号为 $k$，记 $p=k+nx{t}_k-1$。
为什么不是 $0\le x<n$？因为 $nx{t}_0$ 一定等于 $n$，这样子就没什么意义了。
根据定义，我们可以得到 $b_{\mathrm{0...}nx{t}_k-1}==b_{k...p}$ 。如图，蓝色部分相等：

于是，我们就可以推出：$b_{x-k...nx{t}_k-1}=b_{x...p}$

我们最终的目的是求出 $nx{t}_x$，$x$ 对应的位置是 $x-k$，所以我们要根据 $x-k$ 判断 $x$能跳多远。
令 $l=nx{t}_{x-k}$，如果 $x-k+l-1$ 还在绿色区域范围内，也就是 $x-k+l-1\le nx{t}_k-1$，那么 $b_{x-k...x-k+l-1}==b_{x...x+l-1}$。如图，灰色部分相等：

但是如果它超出了绿色部分，超出的部分就不能保证相等了，要暴力匹配。如图：

这个过程是不是和Manacher一毛一样？

vector<int> getNext(string &s)
{vector<int> nxt(s.size());int p=0; //furthest position p=k+nxt[k]-1int k=1; //furthest position idnxt[0]=s.size();while(p+1<s.size()&&s[p]==s[p+1])p++;nxt[1]=p;for(int i=2; i<s.size(); i++){p=k+nxt[k]-1;int l=nxt[i-k]; //if i+l<=p then [i,i+l-1] == [i-k,i-k+l-1]if(i+l<=p) nxt[i]=l;else{int j=max(0ll,p-i+1);while(i+j<s.size()&&s[i+j]==s[j])j++;nxt[i]=j;k=i;}}return nxt;
}

求解 extend 数组（z函数）

和求解 $nxt$ 数组的过程类似。

vector<int> getExtend(string &s,string &t,vector<int> &nxt)
{int p=0,k=0;while(p<s.size()&&p<t.size()&&s[p]==t[p]) p++;vector<int> ext(s.size());ext[0]=p;for(int i=1; i<s.size(); i++){p=k+ext[k]-1;int l=nxt[i-k];if(i+l<=p) ext[i]=l;else{int j=max(0ll,p-i+1);while(i+j<s.size()&&j<t.size()&&s[i+j]==t[j])j++;ext[i]=j;k=i;}}return ext;
}

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

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+7,inf=1e18;
vector<int> getNext(string &s)
{vector<int> nxt(s.size());int p=0; //furthest position p=k+nxt[k]-1int k=1; //furthest position idnxt[0]=s.size();while(p+1<s.size()&&s[p]==s[p+1])p++;nxt[1]=p;for(int i=2; i<s.size(); i++){p=k+nxt[k]-1;int l=nxt[i-k]; //if i+l<=p then [i,i+l-1] == [i-k,i-k+l-1]if(i+l<=p) nxt[i]=l;else{int j=max(0ll,p-i+1);while(i+j<s.size()&&s[i+j]==s[j])j++;nxt[i]=j;k=i;}}return nxt;
}
vector<int> getExtend(string &s,string &t,vector<int> &nxt)
{int p=0,k=0;while(p<s.size()&&p<t.size()&&s[p]==t[p]) p++;vector<int> ext(s.size());ext[0]=p;for(int i=1; i<s.size(); i++){p=k+ext[k]-1;int l=nxt[i-k];if(i+l<=p) ext[i]=l;else{int j=max(0ll,p-i+1);while(i+j<s.size()&&j<t.size()&&s[i+j]==t[j])j++;ext[i]=j;k=i;}}return ext;
}
void O_o()
{string s,t;cin>>s>>t;auto nxt=getNext(t);auto ext=getExtend(s,t,nxt);int a=0,b=0;for(int i=0; i<nxt.size(); i++){a^=(i+1)*(nxt[i]+1);}for(int i=0; i<ext.size(); i++){b^=(i+1)*(ext[i]+1);}cout<<a<<"\n"<<b<<"\n";
}
signed main()
{ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);cout<<fixed<<setprecision(12);int T=1;
//	cin>>Twhile(T--){O_o();}
}