【学习笔记】exkmp（Z函数）

本文参考洛谷题解：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]-1
	int k=1; //furthest position id
	nxt[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]-1
	int k=1; //furthest position id
	nxt[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>>T
	while(T--)
	{
		O_o();
	}
}