526互联

【GJOI 2023.11.13 T2】 字符串匹配

发布时间 2023-11-14 20:46:50作者: dijah

字符串匹配

题意：给出两个字符串 \(a,b\) ，求：

\[\sum_{1 \le l \le r\le n} \sum_{l\le i \le j\le r}(a[l...r] 回文)(a[i...j]==b) \times (r-l+1) mod 2 \]

其中 \(n,m \le 10^6\) 。

解题思路

首先，因为 \(a[l..r]\) 长度为奇数，它又要回文，所以它一定是要有一个回文中心的。
那我们可以先用马拉车算法求出以一个节点为中心的最大回文半径，再用 \(KMP\) 求出 \(b\) 在 \(a\) 中哪里出现过，最后就看 \(b\) 在 \(a\) 中时被回文串一共包含多少次。
对于这个东西，我们可以先用树状数组做，但这样做会被卡常。
我们就可以用前缀和来代替，对于每个节点，考虑在其前半个字符串的 \(b\) 以及在其后半个字符串的 \(b\) ，用前缀和 \(v_i\) 与前缀和 \(i\times v_i\) 来解决。
时间复杂度 \(O(n)\) 。

Code

#include<bits/stdc++.h>
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
using namespace std;
const long long mod=4294967296;
int n,m,d[3000005],nxt[3000005],f[6000005],g;
long long f1[6000005],d1[3000005],d2[3000005];
bool v[3000005];
string a,b;
int lowbit(int x)
{
	return x&(-x);
}
void next()
{
	nxt[0]=-1;
	int x=1,y=-1;
	while(x<b.size())
	{
		while(y>=0&&b[x]!=b[y+1])y=nxt[y];
		if(b[x]==b[y+1])y++;
		nxt[x]=y;
		x++;
	}
	return;
}
void KMP()
{
	next();
	int x=0,y=-1;
	while(x<a.size())
	{
		while(y>=0&&(y==m-1||a[x]!=b[y+1]))y=nxt[y];
		if(a[x]==b[y+1])y++;
		if(y==m-1)v[x-y]=true;
		x++;
	}
	return;
}
int main()
{
	long long s=0,y=0;
	int x=0,p=0,mid;
	scanf("%d%d",&n,&m);
	g=n*2;
	cin>>a>>b;
	a=' '+a;
	for(int i=1;i<a.size();i++)
	{
		if(x+d[x]>=i)d[i]=min(d[x*2-i],d[x]+x-i);
		while(d[i]<i&&i+d[i]<a.size()-1&&a[i-d[i]-1]==a[i+d[i]+1])d[i]++;
		if(x+d[x]<i+d[i])x=i;
	}
	KMP();
	for(int i=1;i<=n;i++)
	{
		d1[i]=d1[i-1]+v[i];
		d2[i]=d2[i-1]+v[i]*i;
	}
	for(int i=1;i<=n;i++)
	{
		x=i-d[i],y=i+d[i]-m+1;
		mid=(x+y)>>1;
		if(x>y)continue;
		s+=(d2[mid]-d2[x-1])-(d1[mid]-d1[x-1])*(x-1);
		if(x!=y)s+=(y+1)*(d1[y+1]-d1[mid])-(d2[y+1]-d2[mid]);
		s%=mod;
	}
	printf("%lld",s);








  return 0;
}