NOIP2020 字符串匹配
这里只讲满分做法
首先,这道题肯定要枚举字符串的长度。考虑到枚举C的长度还需要再枚举AB来验证,而仅仅枚举A就不可避免地还要枚举B的长度。所以我们考虑枚举AB的长度,然后再通过C计算此时对答案的贡献
接下来就考虑两件事情:
- 1.AB能延伸到多远
- 2.如何计算合法的A、C的数量
先看第一个问题,AB能延伸到多远,就是说往后有多少个重复的AB。这个可以通过倍增+hash计算,单次最高复杂度为log级,但实际上由于AB长度不断增大,该部分复杂度均摊差不多logln,非常小。
再看第二个问题。考虑判定一组AC合法的条件:
F( A )<=F( C ),其中F表示某一字符串内出现奇数次的字符有多少个
并且可以发现,A,C分别为前缀/后缀字串,于是考虑预处理前/后缀子串的F值,这一步预处理复杂度O(n)
而后需要注意到C串的一个性质:对于每一个AB,C的“本质”至多有两种,且仅与AB的重复次数奇偶性有关。也就是说,至多有两种F(C)。于是经过预处理之后,计算两种F(C)的复杂度为O(1)。
接下来,只需要分奇偶讨论每种F(C)对应多少种A串即可。在实现时,用sum[x]统计F值为x的前缀子串有多少个,乘上该种贡献被统计了几次。
A确定,B串就确定了,不需要再进行讨论。
#include<bits/stdc++.h>
using namespace std;
#define ULL unsigned long long
#define LL long long
#define il inline
#define re register
il int read()
{
int s=0,w=1;char c=getchar();
while(c<'0'||c>'9'){ if(c=='-') w=-1;c=getchar();}
while(c>='0'&&c<='9'){ s=(s<<1)+(s<<3)+c-'0';c=getchar();}
return s*w;
}
const ULL base=131ULL;
const int N=(1<<20)+100;
int T,n;
char s[N];
ULL a[N],pwer[N];
int num[30],Fl[N],Fr[N],sum[N];
/*
num暂时记录每一种字符出现次数
Fl/Fr分别对应前缀/后缀数组,表示到某一个位置出现奇数次的字符数量
c1,c2分别表示C的两种“本质”,即两种题干中的F值
sum表示有多少个前缀的奇数字符数为x
*/
ULL get_hash(int l,int r){ return a[r]-a[l-1]*pwer[r-l+1]; }
il bool check(int len,int r,int p)
{//r表示的是AB的重复次数
return get_hash((r-p)*len+1,r*len)==get_hash(r*len+1,(r+p)*len);
}
il void Init()
{
memset(a,0,sizeof(a));
memset(num,0,sizeof(num));
memset(sum,0,sizeof(sum));
memset(Fl,0,sizeof(Fl));
memset(Fr,0,sizeof(Fr));
}
int main()
{
pwer[0]=1ULL;
for(re int i=1;i<=1048580;i++) pwer[i]=pwer[i-1]*base;
T=read();
while(T--){
Init();
LL ans=0;
scanf("%s",s+1);n=strlen(s+1);
for(re int i=1;i<=n;i++) a[i]=s[i]-'a'+1;
//-------------预处理--------
for(re int i=1;i<=n;i++){
num[a[i]]^=1;
Fl[i]=(num[a[i]])?Fl[i-1]+1:Fl[i-1]-1;
}
memset(num,0,sizeof(num));
for(re int i=n;i>=1;i--){
num[a[i]]^=1;
Fr[i]=(num[a[i]])?Fr[i+1]+1:Fr[i+1]-1;
}
for(re int i=1;i<=n;i++) a[i]+=a[i-1]*base;
//----------主体------------
for(re int i=1,c1,c2;i<n;i++){//枚举AB串的长度
c1=Fr[i+1];
c2=((i<<1)<n)?Fr[i<<1|1]:-1;
//--------------倍增-----------------
int p=1,r=1;
while(p>0){
if(1LL*(r+p)*i<1LL*n && check(i,r,p)) r+=p,p<<=1;
else p>>=1;
}
//-------------分奇偶讨论-----------
for(re int j=0;j<=c1;j++) ans+=sum[j]*((r+1)>>1);
for(re int j=0;j<=c2;j++) ans+=sum[j]*(r>>1);
/*这里,((r+1)>>1)与 (r>>1)分别表示AB串重复次数为奇
的方案数 和 重复次数为偶的方案数
*/
sum[Fl[i]]++;//在递推的过程中统计sum数组
}
printf("%lld\n",ans);
}
}