自动搬运

查看原文

来自洛谷，原作者为

	mcqueen OI has been the glory of my adolescence.

搬运于2025-08-24 22:05:55，当前版本为作者最后更新于2020-02-16 22:50:47，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

大家好，我喜欢打暴力，所以我用暴力哈希 AC 了这道题。

观察题目，便可得知需要拆环，将原字符串复制一份放到原字符串后即可。此时，字符串$S$的长度为$2n$。

设$a=(l-1)/2$，我们需要从$S_{a+1}$到$S_{n+a}$中枚举回文中心。

对字符串$S$正反分别做一次哈希，在枚举过程中，若位置$i$满足字符串中$[i-a,i-1]$上的正哈希值等于$[i+1,i+a]$上的反哈希值，说明这个位置是回文串的回文中心，这时候答案加一即可。

为了避免哈希冲突，我选择使用双哈希，即使用了两个神奇的质数作为底数。当然，如果您有信仰的话，也可以选择单哈希。

1A代码：

#include<bits/stdc++.h>
#define ull unsigned long long
#define N 1000005
using namespace std;
char s[N<<1];
ull LtoR1[N<<1],RtoL1[N<<1],LtoR2[N<<1],RtoL2[N<<1],mul1[N<<1],mul2[N<<1];
int n,l;
const ull p1=19260817,p2=19491001;
inline bool check(int l,int r,ull LtoR[],int L,int R,ull RtoL[],ull mul[])
{
	ull hs1=LtoR[r]-LtoR[l-1],hs2=RtoL[L]-RtoL[R+1];
	int t=n+n-r+1;
	if(t>L)hs2*=mul[t-L];
	if(L>t)hs1*=mul[L-t];
	return hs1==hs2;
   //写一个函数减少写代码难度。
}
int main()
{
	scanf("%d%d",&n,&l);
	if(l==1){printf("%d\n",n);return 0;}//特判一下，防止出现奇怪的问题
	scanf("%s",s+1);
	for(int i=1;i<=n;++i)s[i+n]=s[i];
	
	mul1[0]=mul2[0]=1;
	for(int i=1;i<=n+n;++i)
	mul1[i]=mul1[i-1]*p1,
	mul2[i]=mul2[i-1]*p2;
	
	for(int i=1;i<=n+n;++i)
	LtoR1[i]=LtoR1[i-1]+s[i]*mul1[n+n-i+1],
	LtoR2[i]=LtoR2[i-1]+s[i]*mul2[n+n-i+1];
	
	
	RtoL2[n+n]=s[n+n]*mul2[n+n];
	RtoL1[n+n]=s[n+n]*mul1[n+n];
	
	for(int i=n+n-1;i>=1;--i)
	RtoL1[i]=RtoL1[i+1]+s[i]*mul1[i],
	RtoL2[i]=RtoL2[i+1]+s[i]*mul2[i];
	
	
	l=(l-1)>>1;
	int ans=0;
	for(int i=l+1;i<=n+l;++i)//注意是从‘l+1’到‘n+l’，细节问题不要搞错了！
	{
		if(check(i-l,i-1,LtoR1,i+1,i+l,RtoL1,mul1)&&check(i-l,i-1,LtoR2,i+1,i+l,RtoL2,mul2))
		++ans;		
	}
	printf("%d\n",ans);
	return 0;
}