$$Manacher$$
【杂言】 ：
任何的字符串算法在刚进行的时候，都会感觉很有难度， 唯一解决难度的问题， 就是多打多练，例如(Manacher),自然，也是有大佬直接一眼就可以看懂的，这也是我的一点理解
【准备】：
这也大多数的回文字符串可能用的，单独列一下。
- 首先在字符串的每一个字符之前或者之后都加入一个#，举个例子 ：例如字符串(S = "abcd") , 根据这个意思，我们也就是要把他变成 (S=) "#a#b#c#d#" 至于为什么这么做？因为在进行回文字符串的判定时 ，字符串长度是偶数或奇数都会导致有不同的实现 ， 十分的麻烦，同时，相比之下， 长度为奇数的 回文字符串更好判定， 所以转化为上述形式。关于一定会形成奇数的证明（相当于字符串 ( imes 2 +) #）。
- 为了防止每一次进行询问的时候都看一下是否会越界，我们在首尾添加上一个^和~,这种东西，当询问到那里的时候自动跳出就行了
- 但同时我们插入的这些所有的 字符，都必须保证和原字符保持互异 。
综上 ， 也就是把上面的字符串 ，改成了(S= ") ~#a#b#c#d#^(") 的这么一个基操，其实在普通的回文字符串的判定，基本上也会用到来优化代码；
【算法】:
通过举出一个例子来进行说明一下算法的流程;
例子 ： (S="abbahopo") ,我们发现在本串(S)中存在两个回文子串， 一个是长度为偶数的子串("abba")，和长度为奇数的回文子串 ，("opo")，我们按照上方的准备，魔改一下，就出来了新的(S)（仍旧选用(S),应该是(S_{new})的）,= " ~ #a#b#b#a#h#o#p#o# ^ ",经过魔改之后，其长度也就都是奇数了，然后再来考虑一下其寻找过程。
由于下面插入在使用(Markdown)时，用,#会导致语法异常，在这里省略掉开头和结尾的^，并且用(1)来代替#。
定义数组 (len_i) ,用于保存字符(i)的最大扩展长度，也就是回文半径， 同时 ， 它也是去掉我们加的#字符的原数组的该扩展的字符串的总长度，例如下图中#o#p#o#，其最大回文半径就是(3),并且，该字符串的长度也就是(3)。
则，其回文字符串的长度，就是(len_{i}) - 1
重点就是对于(len_i)的求解，
设置两个变量(mx)和(id) ，(mx)表示以(id)为中心的最长的回文子串的右边界， 那么则有，(mx = id + len_{id}) ,
如上图，假设我们现在进行求解(len_i),
也就是以(i)为中心最长回文半径，如果(i<mx)那就是上图， (len_i=min(len_{id * 2 - i} ,mx-i)) ,其中(len_{id * 2 - i})就是(i)关于(id)的对称点 ， 即上图的(len_{j})
【复杂度】：
关于这个算法的复杂度， 显然我不会证明， 但是线性的。
结合下文的参考文献吧
【参考文献】：
1.https://segmentfault.com/a/1190000008484167
2.https://www.zhihu.com/question/37289584（这个倒是多）
【例题】：
给出一个只由小写英文字符 ( exttt a, exttt b, exttt c,ldots exttt y, exttt z)组成的字符串 (S) ,求 (S) 中最长回文串的长度 。
/*
by : Zmonarch
知识点 ： Manacher
*/
#include <bits/stdc++.h>
using namespace std ;
const int kmaxn = 1e8 ;
int len[kmaxn] , ans;
int mx , id ,cnt ;
char s[kmaxn] , s1[kmaxn] ;//s1是旧的，s是新的
void prepare()
{
//将原来的字符串搞出来
scanf("%s" , s1 +1) ;
int n = strlen(s1+1) ;
s[++cnt] = '~' ;
s[++cnt] = '#' ; //第一个数之前别忘了插入
for(int i = 1 ; i <= n ; i++)
{
s[++cnt] = s1[i] ;
s[++cnt] = '#' ;
}
s[++cnt] = '^' ;
}
void manacher()
{
for(int i = 2 ; i <= cnt - 1; i++)//过滤掉首尾的标示符
{
if(i <= mx) len[i] = min(len[id * 2 - i ] , mx - i + 1) ;
else len[i] = 1 ;
while(s[i - len[i]] == s[i + len[i]])
{
len[i]++;
}
if(i + len[i] > mx)
{
mx = i + len[i] - 1 ;
id = i ;
}
//printf("%d
", ans) ;
ans = max(ans , len[i]) ;
}
printf("%d", ans-1) ;
}
int main()
{
prepare() ;
manacher() ;
return 0 ;
}