字符串匹配
题意:给出两个字符串 \(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;
}
标签:13,le,int,2023.11,T2,long,3000005,d2,d1
From: https://www.cnblogs.com/dijah/p/17832486.html