Manacher马拉车

俗话说：摩托再好，不如骡拉啊(好像不是骡）

Manacher就是O(N)计算最长回文子串的算法。

其中我们需要在0位置加入字符“$"，然后原字符串中每两个字符加入一个"#"。

算法中 id 为当前最长回文子串的中心 mx为当前最长回文子串的右侧位置。

每做到一个i，若mx>i，则p[i]=min(mx-i,p[2*id-i]),否则为1，然后暴力拓展。

证明什么的网上一大堆了。。

模板题：hdu3068

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<string>
 6 #include<algorithm>
 7 char s[250005],a[250005];
 8 int p[250005];
 9 int main(){
10     while (~scanf("%s",s)){
11         int len=1,l1=strlen(s);
12         a[0]='$';
13         for (int i=0;i<l1;i++){
14             a[len++]='#';
15             a[len++]=s[i];
16         }
17         a[len]='#';
18         int mx=0,id=0;
19         memset(p,0,sizeof p);
20         for (int i=1;i<=len;i++){
21             if (mx>i){
22                 p[i]=(mx-i<p[2*id-i])?mx-i:p[2*id-i];
23             }
24             else
25                 p[i]=1;
26             while (a[i-p[i]]==a[i+p[i]]) p[i]++;
27             if (i+p[i]>mx){
28                 mx=i+p[i];
29                 id=i;
30             }   
31         }
32         int ans=0;
33         for (int i=1;i<=len;i++)
34          if (ans<p[i]) ans=p[i];
35         printf("%d
",ans-1); 
36     }
37 }