BZOJ 3790: 神奇项链 [Manacher 贪心]

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int N=1e5+5;
int n;
char s[N],str[N];
void iniStr(char *str,char *s){
    for(int i=1;i<=n;i++)
        s[(i<<1)-1]=‘#‘,s[i<<1]=str[i];
    s[0]=‘$‘;s[n<<1|1]=‘#‘;
}
int r[N];
void Manacher(char *s,int n){
    int p=0,a;
    for(int i=1;i<=n;i++){
        r[i]=i<p?min(p-i+1,r[2*a-i]):1;
        while(s[i-r[i]]==s[i+r[i]]) r[i]++;
        if(i+r[i]-1>p) p=i+r[i]-1,a=i;
    }
}
struct Seq{
    int l,r;
    bool operator <(const Seq &a) const{
        return l<a.l||(l==a.l&&r>a.r);
    }
}a[N];
void solve(){
    n=n<<1;
    for(int i=1;i<=n;i++) a[i].l=i-r[i]+1,a[i].r=i+r[i]-1;
    sort(a+1,a+1+n);
    int now=a[1].r+1,ans=1,r,i=2;
    while(now<=n){
        r=0;
        while(i<=n&&a[i].l<=now) r=max(r,a[i].r),i++;
        now=r+1;
        ans++;
    }
    printf("%d\n",ans-1);
}
int main(){
    freopen("in","r",stdin);
    while(scanf("%s",str+1)!=EOF){
        memset(r,0,sizeof(r));
        memset(s,0,sizeof(s));
        n=strlen(str+1);
        iniStr(str,s);
        Manacher(s,n<<1);
        solve();
    }
}