题解 P4987 【回文项链】

mcqueen · 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;
}