manacher 算法
概述
-
manacher 算法是一种通过 来高效地找出字符串的回文子串的算法。
-
我们知道极限情况下回文子串的总数可以达到
n^2 （n=len ，下同），所以我们只找出每个“极大回文子串”，即无法继续向左右延伸的回文子串。
实现原理
-
预处理：
aabaaaab -> ^#a#a#b#a#a#a#a#b#@。注意，这并不是 manacher 算法特有的预处理。 -
其中首尾处的占位符并不必要，但可以省去越界判断的繁琐。
-
观察可知，原本的奇数长度回文串被塞了偶数个“#”（注意这也只是一个占位符，只要
\notin S ，我们不关心它是什么），仍为奇数长度回文串；而原本的偶数长度回文串被塞了奇数个，变成了奇数长度回文串。 -
从而我们绕过了“虚空对称中心”的问题。
-
不妨定义“半径”为从对称中心开始（不含）向左/右延伸的最大长度。
-
容易看出，半径即为原回文子串长度。
-
下面我们故技重施：利用自动机思想，设法从已经算出的回文子串中获得一些信息。
-
定义
l,r 为回文子串的左右端点。维护有最大r 的对称中心C 及其l,r （下文l,r 均指C 的）。
- 观察上图。可以看到，
C 两侧长度为R （半径）的两段互为镜像。模仿z 函数的算法，我们有：
-
可以看出，暴力单次
O(1) ，每次暴力至少会使r+1 ，而r\leqslant n 。非暴力单次O(1) ，至多n 次。 -
从而我们有着
O(n) 的优秀复杂度。
int p[maxn];//此p为半径。
il void manacher(string &S){
string s="^#";
For(i,0,(int)S.size()-1) s+=S[i],s+="#";
s+="$";
int to=s.size()-1,C=0,r=0;
For(i,1,to){
int ii=(C<<1)-i;
if(r>i) p[i]=min(r-i,p[ii]);
while(s[i+p[i]+1]==s[i-p[i]-1]) ++p[i];
if(i+p[i]>r) r=i+p[i],C=i;
ans=max(ans,p[i]);
}
return;
}