马拉车算法——poj3974
https://segmentfault.com/a/1190000008484167?tdsourcetag=s_pctim_aiomsg 讲的超好！
manacher算法理解
回文串分为偶回文串和奇回文串，由于偶回文串无法找到中点，所以这里将偶回文串转换为奇回文
转换方法s="abcde"=>s="$#a#b#c#d#e#"
数组p[i]，表示以i为中心的最长回文的半径，p[i]-1刚好是以i为中心的源字符串中的回文长度
从左往右扫描s，求出p数组
mx:延伸到最右边的回文的边界(不包含 )
id:mx对应的中点
现在扫到了i，i关于id对称点是j，p[j]已知，以下分三种种情况
1.i<mx:p[i]=min(p[j],mx-i)，i在mx左边
2.i>=mx:p[i]=1 ，i在mx的右边
3.往两边拓展边界
求出p[i]后更新mx即可
为什么复杂度是on？
当且仅当j的边界和mx重合时，i才要向两边扩展，
#include<bits/stdc++.h> using namespace std; #define maxn 100005 char s[maxn],s_new[maxn]; int p[maxn]; int init(){ int len=strlen(s); s_new[0]='$',s_new[1]='#'; int j=2; for(int i=0;i<len;i++) s_new[j++]=s[i],s_new[j++]='#'; s_new[j]='