Manacher算法？？？

　　Mancher算法是用来找最大回文串的，因为功能太过单一，所以用处不是很多，但是在找回文串方面还是很强大的。

大致原理：

　　枚举回文串的中点，用p[i]表示以i为中心的最大回文串的长度。然后对p[i]进行扩展就可以了。

　　　　最简单的扩展就是当s[i+p[i]+1]=s[i-p[i]-1]的时候p[i]就可以加一。

　　　　然后就是对上面进行一下优化，用一个id来记录可以延伸的最靠右的回文串的中心，mx为其长度。然后对于枚举到的中心i如果i没有超过id+mx,说明在id前面一定有一个j与i相同，并且j已经处理过了，所以就可以直接将p[i]=p[j]但是需要注意的是，如果i+p[j]超出了mx，就不能保证这是个回文串了，p[i]=min(p[id-(i-id)],mx-i)    这里的id-(i-id)就是上面的j

　　　　同时不断地更新id和mx并且记录下最大的p[i]就行了。

一道板子题：luogu3805

代码：

 1 #include<vector>
 2 #include<queue>
 3 #include<ctime>
 4 #include<algorithm>
 5 #include<deque>
 6 #include<cstdlib>
 7 #include<string>
 8 #include<cstring>
 9 #include<map>
10 #include<bitset>
11 #include<cstdio>
12 #include<iostream>
13 #define max(x,y) x>y?x:y
14 using namespace std;
15 typedef long long LL;
16 void read(int &x){
17     x=0;int f=1;char c=getchar();
18     while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
19     while(c>='0'&&c<='9') { x=x*10+c-'a';c=getchar();}x*=f;
20 }
21 const int N=11000000+10;
22 char s[N],S[N*2];
23 int ans,len,id,mx,p[N*2];
24 inline void manacher()
25 {
26     for(int i=1;i<=len;++i)
27     {
28         if(id+mx>i)
29         p[i]=min(id+mx-i,p[id*2-i]);
30         while(i+p[i]+1<=len&&i-p[i]-1>=1&&S[i+p[i]+1]==S[i-p[i]-1]) p[i]++;
31         if(i+p[i]>id+mx) id=i,mx=p[i];
32         ans=max(ans,p[i]);
33     }
34     printf("%d",ans);
35 }
36 
37 int main()
38 {
39     cin>>s;
40     int l=strlen(s);
41     S[++len]='#';
42     for(int i=0;i<l;++i)
43     {
44         S[++len]=s[i];
45         S[++len]='#';
46     }
47     manacher();
48     
49     return 0;
50 }