神奇项链（manacher）

神奇项链

描述

母亲节就要到了，小 H 准备送给她一个特殊的项链。这个项链可以看作一个用小写字母组成的字符串，每个小写字母表示一种颜色。为了制作这个项链，小 H 购买了两个机器。第一个机器可以生成所有形式的回文串，第二个机器可以把两个回文串连接起来，而且第二个机器还有一个特殊的性质：假如一个字符串的后缀和一个字符串的前缀是完全相同的，那么可以将这个重复部分重叠。例如：aba和aca连接起来，可以生成串abaaca或 abaca。现在给出目标项链的样式，询问你需要使用第二个机器多少次才能生成这个特殊的项链。

输入

输入数据有多行，每行一个字符串，表示目标项链的样式。
每个测试数据，输入不超过 5行
每行的字符串长度小于等于 50000

输出

多行，每行一个答案表示最少需要使用第二个机器的次数。

样例

输入

abcdcba 
abacada 
abcdef

输出

0
2
5

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 char s[1000001],s_new[3000000];
 4 int p[3000000];
 5 struct data{
 6     int l,r;
 7 }a[10000001];
 8 bool cmp(data x,data y)
 9 {
10     if(x.l==y.l)
11     return x.r>y.r;
12     else
13     return x.l<y.l;
14 }
15 int get()
16 {
17     s_new[0]='$';
18     s_new[1]='#';
19     int k=2;
20     int len=strlen(s);
21     for(int i=0;i<len;i++)
22     {
23         s_new[k++]=s[i];
24         s_new[k++]='#';
25     }
26     s_new[k]='';
27     return k;
28 }
29 int manacher()
30 {
31     int len=get();
32     int id=0,mx=0;
33     for(int i=1;i<len;i++)
34     {
35         if(i<mx)
36         p[i]=min(mx-i,p[2*id-i]);
37         else
38         p[i]=1;
39         while(s_new[i-p[i]]==s_new[i+p[i]])
40             p[i]++;
41         if(mx<i+p[i])
42         {
43             id=i;
44             mx=i+p[i];
45         }
46         a[i].l=i-p[i]+1,a[i].r=i+p[i]-1;
47     }
48     sort(a+1,a+len,cmp);
49     int ans=0,q=0,i=1;
50     while(i<len)
51     {
52         int sum=0;
53         while(a[i].l-1<=q)
54         {
55             sum=max(sum,a[i].r);
56             i++;
57         }
58         ans++;
59         q=sum;
60         if(q==len-1)
61         break;
62     }
63     return ans-1;
64 }
65 int main()
66 {
67     while(scanf("%s",s)!=EOF)
68         printf("%d
",manacher());
69     return 0;
70 }