如何用 KMP 偏序 Z 函数

KMP 算法求解字符串匹配的过程中 \(next\) 数组有着繁多的应用，主要是可以帮我们求 border。

然而用 \(s\) 串匹配 \(t\) 串产生的 \(f\) 数组应用相对较少。

\(f\) 数组的实际意义就是与当前考虑的 \(t\) 串前缀的某个后缀相同的长度最大的 \(s\) 串前缀。所有与 \(t\) 串该前缀的后缀匹配的 \(s\) 串前缀可以通过这个前缀跳 border 得来。

那么我们回忆 LCP 的暴力求法：从两个起始位置 \(i,j\) 暴力匹配，找到第一个 \(k\) 满足 \(s_{i+k}\neq s_{j+k}\)，\(k\) 就是答案。

现在如果对于一个跟当前串 \(t[1,i]\) 后缀匹配的 \(s\) 串前缀 \(j\) 满足 \(s_{j+1}\neq t_{i+1}\)，那么显然有 \(z_{i-j+1}=j\)。

暴力跳所有的匹配的 \(s\) 串前缀复杂度肯定无法接受，但我们发现我们只需要找到所有 \(s_{j+1}\neq t_{i+1}\) 的匹配前缀即可。而由于每个位置的 LCP 只会在它失配的位置处计算一次，所以如果能快速找到这些前缀均摊下来就是 \(O(n)\) 的。

具体地，跟动态 border 的维护方式很类似，我们只需要在 \(nxt\) 树上预处理跳父亲跳到的第一个后继字符不同的位置。这个预处理可以边求 \(nxt\) 边做，只需要一遍循环就搞定了。代码还是比较好写的。

#include <cstdio>

#include <cstring>

using namespace std;

const int N=20000003;

typedef long long ll;

char t[N],s[N];

int n,m;

int nxt[N],f[N],z[N],w[N];

int main(){

	scanf("%s",t+1);m=strlen(t+1);

	scanf("%s",s+1);n=strlen(s+1);s[n+1]='#';

	for(int i=2,j=0;i<=n;++i){

		while(j&&s[j+1]!=s[i]) j=nxt[j];

		if(s[j+1]==s[i]) ++j;

		nxt[i]=j;

		if(s[i+1]==s[j+1]) f[i]=f[j];

		else f[i]=j;

		int p=j;

		while(p){

			if(s[p+1]!=s[i+1]) z[i-p+1]=p,p=nxt[p];

			else p=f[p];

		}

	}

	z[1]=n;

	for(int i=1,j=0;i<=m;++i){

		while(j&&s[j+1]!=t[i]) j=nxt[j];

		if(s[j+1]==t[i]) ++j;

		int p=j;

		while(p){

			if(s[p+1]!=t[i+1]) w[i-p+1]=p,p=nxt[p];

			else p=f[p];

		}

	}

	ll valz=0,valw=0;

	for(int i=1;i<=n;++i) valz^=(ll)i*(z[i]+1);

	for(int i=1;i<=m;++i) valw^=(ll)i*(w[i]+1);

	printf("%lld\n%lld\n",valz,valw);

	return 0;

}

如何用 KMP 偏序 Z 函数的相关教程结束。