Z-function

用更容易理解的方法处理出

s[l…………r]=s[1…………r-l+1]

常数比KMP略大，时间复杂度\(O(n)\)，方法和manacher很像

#include<bits/stdc++.h>

using namespace std;

#define rint register int

const int N=20000010;

char a[N],b[N];

int z[N],p[N];

long long ans;

inline void Z_function(char *a) {

	int n=strlen(a+1);

	z[1]=n;for(rint i=2;i<=n;++i)z[i]=0;

	for(rint i=2,l=0,r=0;i<=n;++i) {

		if(i<=r)z[i]=min(z[i-l+1],r-i+1);

		while(i+z[i]<=n&&a[i+z[i]]==a[z[i]+1])++z[i];

		if(i+z[i]-1>r)l=i,r=i+z[i]-1;

	}

}

inline void exkmp(char *a,char *b) {

	int n=strlen(a+1);

	for(rint i=1;i<=n;++i)p[i]=0;

	for(rint i=1,l=0,r=0;i<=n;++i) {

		if(i<=r)p[i]=min(z[i-l+1],r-i+1);

		while(i+p[i]<=n&&a[i+p[i]]==b[p[i]+1])++p[i];

		if(i+p[i]-1>r)l=i,r=i+p[i]-1;

	}

}

int main() {

	scanf("%s%s",a+1,b+1);

	Z_function(b);ans=0;for(rint i=1,m=strlen(b+1);i<=m;++i)ans^=1ll*(z[i]+1)*i;printf("%lld\n",ans);

	exkmp(a,b);   ans=0;for(rint i=1,n=strlen(a+1);i<=n;++i)ans^=1ll*(p[i]+1)*i;printf("%lld\n",ans);

	return 0;

}

这东西也可以做字符串匹配。把模式串接在文本串前面，跑一遍Z-function，找到 \(Z_i \geq lenb\) 的即可

巴特西

Z-function

最新文章

热门文章