[BZOJ3790]神奇项链

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #define M 100010
 6 using namespace std;
 7 int n,N,ans,now,r,mx;
 8 int len[M],p[M]; 
 9 char a[M],s[M*2];
10 void change()
11 {
12     s[0]=‘&‘;
13     for(int i=0;i<N;i++)
14     {
15         s[++n]=‘#‘;
16         s[++n]=a[i];
17     }
18     s[++n]=‘#‘;
19 }
20 void manacher()
21 {
22     int maxright=0,mid;
23     for(int i=1;i<=n;i++)
24     {
25         if(i<maxright) len[i]=min(len[mid*2-i],maxright-i);
26         else len[i]=1;
27         while(s[i-len[i]]==s[i+len[i]]) len[i]++;
28         if(len[i]+i>maxright)
29         {
30             maxright=len[i]+i;
31             mid=i;
32         }
33     }
34 }
35 struct point{
36     int l,r;
37 }b[M];
38 bool cmp(point a1,point a2) {return a1.l<a2.l||(a1.l==a2.l&&a1.r>a2.r);}
39 int main()
40 {
41     while(scanf("%s",a)!=EOF)
42     {
43         N=strlen(a);
44         n=0;
45         int cnt=0;
46         change();
47         manacher();
48         for(int i=1;i<=n;i++) b[++cnt].l=i-len[i]+1,b[cnt].r=i+len[i]-1;
49         sort(b+1,b+1+cnt,cmp);
50         r=b[1].r;ans=1;now=2;
51         while(r<n)
52         {
53             mx=r;
54             while(now<=cnt&&b[now].l<=r)
55             {
56                 mx=max(mx,b[now].r);
57                 now++;
58             }
59             ++ans;r=mx;
60         }
61         printf("%d\n",ans-1);
62     }
63     return 0;
64 }