蒟蒻的小窝

蒟蒻的小窝

题解 P4656 【[CEOI2017]Palindromic Partitions】

posted on 2020-11-28 10:17:17 | under 题解 |

对于这道题,笨蛋的想法就是左边的字符串每次的右边界往右推一个单位,右边的字符串每次左边界往左推一个单位,一但左边从串和右边的串相等时就把长度清 $0$。但每次判断两个串的时效太慢,对于每个串它要出结果时效近似 $L^2$,所以我们想到字符串 $hash$,这样每次判断 $O(1)$ 就没问题,这题就做下来了,但是奇偶要特判一下。

#include<bits/stdc++.h>
using namespace std;
const int TT[2]={1000007,100007};//hash尽量模大的质数,这里开2个也是怕撞车
int t;
int s[2][1000005],S[2][1000005];
char a[1000005];
inline int read(){
    int ret=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}
    while(isdigit(ch)){ret=ret*10+ch-'0';ch=getchar();}
    return ret*f;
}
int main(){
    t=read();S[0][0]=S[1][0]=1;
    while(t--){
        scanf("%s",a+1);int lena=strlen(a+1),st=0,len=1,ed=lena/2,ans=1;
        for(int i=1;i<=lena;i++)S[0][i]=S[0][i-1]*TT[0],s[0][i]=s[0][i-1]+a[i]*S[0][i],S[1][i]=S[1][i-1]*TT[1],s[1][i]=s[1][i-1]+a[i]*S[1][i];
        for(int i=1;i<=ed;i++){
            if((s[0][st+len]-s[0][st])*S[0][lena-st-len-st]==s[0][lena-st]-s[0][lena-st-len]&&(s[1][st+len]-s[1][st])*S[1][lena-st-len-st]==s[1][lena-st]-s[1][lena-st-len]){
                if(st+len<ed+lena%2)ans+=2;else ans++;len=0;st=i;
            }
            len++;
        }
        printf("%d\n",ans);
    }
    return 0;
}