bzoj3790 神奇项链

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<queue>
#include<deque>
#include<set>
#include<map>
#include<ctime>
#define LL long long
#define inf 0x7ffffff
#define pa pair<int,int>
#define pi 3.1415926535897932384626433832795028841971
using namespace std;
inline LL read()
{
    LL x=0,f=1;char ch=getchar();
    while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}
    while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}
    return x*f;
}
inline void write(LL a)
{
	if (a<0){printf("-");a=-a;}
	if (a>=10)write(a/10);
	putchar(a%10+‘0‘);
}
inline void writeln(LL a){write(a);printf("\n");}
int len,cnt,tot,now,ans;
char ch[100010],s[100010];
int p[100010];
struct srt{int l,r;}a[100010];
bool operator <(srt a,srt b){return a.l<b.l||a.l==b.l&&a.r<b.r;}
inline void manacher()
{	
	cnt=tot=0;int mx=0,id=0;
	for (int i=1;i<=len;i++)
	{
		s[++cnt]=‘#‘;
		s[++cnt]=ch[i];
	}
	s[++cnt]=‘#‘;
	s[0]=‘$‘;
	for (int i=2;i<cnt;i++)
	{
		if (p[id]+id>i)p[i]=min(p[2*id-i],p[id]-(i-id));
		else p[i]=1;
		while (s[i+p[i]]==s[i-p[i]])p[i]++;
		if (p[i]+i>p[id]+id)id=i;
	}
	memset(a,0,sizeof(a));
	for (int i=1;i<=cnt;i++)
	{
		int res=p[i]-1;
		int l=i-res,r=i+res;
		if (l%2)l++;if (r%2)r--;
		l/=2;r/=2;
		if (l>r)continue;
		a[++tot].l=l;
		a[tot].r=r;
	}
}
inline void work()
{
	len=strlen(ch+1);
	manacher();
	sort(a+1,a+tot+1);
	now=ans=0;int i=1;
	while (now!=len)
	{
		int to=-1;
		while (a[i].l<=now+1&&i<=tot)
			to=max(to,a[i].r),i++;
		now=to;ans++;
	}
	printf("%d\n",ans-1);
}
int main()
{
	while (~scanf("%s",ch+1))work();
}