NOIP2020 字符串匹配

本文主要是介绍NOIP2020 字符串匹配，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

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); 
	}
}

这篇关于NOIP2020 字符串匹配的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！