(2022牛客多校五)G-KFC Crazy Thursday（二分+哈希）

题目：

样例输入： 

6
kfccfk

样例输出：

3 3 3

题意：给你一个n，以及一个长度为n的字符串，字符串由小写字母组成，然后问里面有多少个分别以k、f、c字母结尾的回文字符串。

这道题好像标解是回文自动机，但是我不太会，下面我说一下这道题二分+哈希的思路以及Manacher优化的思路。

看这道题之前大家应该先会求解一个字符串中的最大回文子串，不会的小伙伴可以看这里：求最大回文子串长度_AC__dream的博客-CSDN博客

首先可以确定的一点是所有的回文串都会有中心字符，如果回文子串长度为奇数，那么就只有一个中心字符，否则就有两个中心字符，所以我们可以枚举以每个字符作为中心时的最长回文串，然后再从中找到以k、f、c结尾的回文串，方法就很简单了，就是说假如我们现在以字符x为中心的最长回文串长度是11，这个长度为11的回文串里面有8个f，那么显然就会有4个以f作为结尾的回文串，毕竟回文串是对称的，所以我们就是这个思路，枚举一下以每个字母作为中心的回文串，事先处理一下k、f、c的数目前缀和，这样可以O(1)判断区间[l,r]里面某个特殊字母出现的次数。注意还有偶数的情况，这个时候就需要枚举一下两个中心点中的一个，左边还是右边都可以，需要注意的就是不存在的情况，就是说两个中心点字母不相同的时候是不存在的情况，二分+哈希求解回文子串长度的方法我已经在之前博客中介绍过了，上面附有博客地址，具体细节见代码：

#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
const int N=5e5+10;
typedef unsigned long long ull;
ull p[N],sum1[N],sum2[N];
int sk[N],sf[N],sc[N];//sx[i]标记前i个位置有多少个字符x 
char s[N];
ull get(int l,int r,int op)
{
	if(op==1)
		return sum1[r]-sum1[l-1]*p[r-l+1];
	else 
		return sum2[l]-sum2[r+1]*p[r-l+1];
}
int main()
{
	int n;
	p[0]=1;
	for(int i=1;i
		p[i]=p[i-1]*131;
	while(scanf("%d",&n)!=EOF)
	{
		scanf("%s",s+1);
		for(int i=1;i<=n;i++)
		{
			sum1[i]=sum1[i-1]*131+s[i];
			if(s[i]=='k') sk[i]=sk[i-1]+1;
			else sk[i]=sk[i-1];
			if(s[i]=='f') sf[i]=sf[i-1]+1;
			else sf[i]=sf[i-1];
			if(s[i]=='c') sc[i]=sc[i-1]+1;
			else sc[i]=sc[i-1];
		}
		sum2[n+1]=0;
		for(int i=n;i>=1;i--)
			sum2[i]=sum2[i+1]*131+s[i];
		long long ansk,ansf,ansc;
		ansk=ansf=ansc=0;
		for(int i=1;i<=n;i++)//枚举长度为奇数情况下第i个位置为中心点的回文子串数目 
		{
			int l=0,r=min(n-i,i-1);
			while(l
			{
				int mid=l+r+1>>1;
				if(get(i-mid,i+mid,1)==get(i-mid,i+mid,2)) l=mid;
				else r=mid-1;
			}
			ansk+=sk[i+l]-sk[i-1];
			ansf+=sf[i+l]-sf[i-1];
			ansc+=sc[i+l]-sc[i-1];
		}
		for(int i=1;i<=n;i++)//枚举长度为偶数情况下第i个位置为两个中心点左边的那个中心点的回文子串数目
		{
			int l=0,r=min(n-i,i);
			while(l
			{
				int mid=l+r+1>>1;
				if(get(i-mid+1,i+mid,1)==get(i-mid+1,i+mid,2)) l=mid;
				else r=mid-1;
			}
			if(l==0) continue;
			ansk+=(sk[i+l]-sk[i-l])/2;
			ansf+=(sf[i+l]-sf[i-l])/2;
			ansc+=(sc[i+l]-sc[i-l])/2;
		}
		printf("%lld %lld %lld\n",ansk,ansf,ansc);
	}
	return 0;
}

Manacher就是对上述查找最大回文子串的一个优化，上述的复杂度是O(nlogn)，而用Manacher优化后的复杂度就是O(n)。只是把找以每个字符为中心的最大回文子串方法进行了优化，不会Manacher算法的小伙伴可以看下这里：Manacher（求解最长回文子串）_AC__dream的博客-CSDN博客

下面就直接附上代码：

#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
const int N=2e6+100;
char s[N];
int p[N],mx,id;
int sk[N],sf[N],sc[N];
int main()
{
	int n;
	cin>>n;
	scanf("%s",s+1);
	for(int i=n;i>=0;i--)
	{
		s[i*2]=s[i];
		s[i*2+1]='#';
	}
	s[0]='$';
	for(int i=1;i<=2*n+1;i++)
	{
		if(s[i]=='k') sk[i]=sk[i-1]+1;
		else sk[i]=sk[i-1];
		if(s[i]=='f') sf[i]=sf[i-1]+1;
		else sf[i]=sf[i-1];
		if(s[i]=='c') sc[i]=sc[i-1]+1;
		else sc[i]=sc[i-1];
	}
	int ansk=0,ansf=0,ansc=0;
	for(int i=1;i<=2*n+1;i++)
	{
		if(imin(p[2*id-i],mx-i);
		else p[i]=1;
		while(i>p[i]&&s[i-p[i]]==s[i+p[i]]) p[i]++;
		if(i+p[i]>mx)
		{
			mx=i+p[i];
			id=i;
		}
		ansk+=(sk[i+p[i]-1]-sk[i-p[i]]+1)/2;
		ansf+=(sf[i+p[i]-1]-sf[i-p[i]]+1)/2;
		ansc+=(sc[i+p[i]-1]-sc[i-p[i]]+1)/2;
	}
	printf("%d %d %d",ansk,ansf,ansc);
	return 0;
}