manacher

求最长回文子串的算法（顺便还能求出来以每个点为中心的最长回文子串）

介绍

先来一道模板题：P3805 【模板】manacher 算法

先考虑一下小学二年级都会的纯暴力解法：以每个字符为中心，向左右扩展直到左右端点不相等为止，这时遍历出来的字符串长度记为这个点的答案，最后结果即为所有点答案取max

很显然，这个方法有两个问题：

1. 无法处理偶数长度的回文字符串。如回文字符串ABBA，实际上不存在一个字符中心可以向外扩展，按照我们的算法，从A、B、B、A四个点扩散出去的答案均为1。当然这个问题并不致命，我们只需要两个字符中间也往外扩展即可。
2. 时间复杂度 \(\Theta(n^2)\) ，稍微大一点的数据都过不了，直接T飞
   
   

过不去那道题？
事实：他数据很大
而暴力是 \(n^2\)
它 最 慢 了！

介绍——马拉车manacher！

首先针对第一个问题，manacher有一个非常巧妙的处理办法：
在每两个字符之间插进去一个统一的字符，比如说'#'。比如我们上文提到的"ABBA"，在做完之后就变成了这样的字符串："#A#B#B#A#"，而"ABA"则变成了"#A#B#A#"。

发现什么了吗？原来长度为奇数的回文字符串中心不变，偶数的回文字符串变成了以'#'为中心的长度为奇数的回文串，而假设我们得到的回文串长度为 \(n\)，由于除法向下取整，答案就直接是 \(n/2\)，我们就可以愉快地向左右枚举了

怎么降低复杂度呢？当然是用万能的字符串哈希了

我们仍然考虑从左往右枚举，只不过这次用 \(len_i\) 记录以每个 \(i\) 为中点的回文串半径（注意：对于只有一个字符的回文串，\(len_i=1\)），用一个变量 \(r\) 记录一下目前处理过的所有点中，最靠右的回文串右端点的右边一个点，再用变量 \(c\) 记录一下该回文串的中点

这个有什么用呢？首先考虑到我们处理到了某一个点 \(i\)，首先，所有 \(j<i\) 都已经被处理完成了。如果满足 \(i<r\)，那么对于 \(i\) 关于 \(c\) 的对称点 \(i'\)，都有 \(len_i>=len_i-1\)

为什么呢？先看下面一张图

\(l\) 为 \(c\) 区间的左端点，左边的黄框为以 \(i'\) 为中心的最长回文串。由于c是最长的回文子串，那么红线连着的两块是对称的，而黄框又关于 \(i'\) 对称，所以照到右边来也是关于 \(i\) 对称的，也就是说 \(len_i\) 最少也得是 \(len_{i'}\)

而由于黄框为最长回文串，所以黄框左右两边的字符一定不同（不然最长回文串长度还能再加），所以对称过去 \(i\) 的黄框左右字符也不同，所以 \(len_i=len_{i'}\)

当然这是黄框没有超过 \(l,r\) 的情况，假如黄框超过了（如下图），那该怎么处理呢？

很简单：直接从 \(r\) 开始（显然在 \(r\) 以前的都能左右配上），暴力往右枚举配对左右端点即可，记得边枚举边更新 \(r\) 和 \(c\)。乍一听这个复杂度会爆炸，别急，我们分析一下复杂度

首先，对于黄框没有超过 \(r\) 的情况，转移显然是 \(\Theta(1)\) 的
考虑黄框超过 \(r\) 的情况，每一次要么往右更新一步（这会使 \(r\) 增加），要么发现左右匹配不上直接break。而 \(r\) 显然是不断递增的，最远也只能到达字符串端点，所以时间复杂度为 \(\Theta(n)\)

而当 \(i>r\) 时，先把 \(len_i\) 赋值为1，再按照黄框超过 \(r\) 的情况处理就好了

基本思想已经介绍完了，上代码

s[0]=114514;
for(int i=0;i<stmp.size();i++){
	s[++cnt]=stmp[i];
	s[++cnt]=114514;//我这里为了更好操作用的int来存字符串，所以间隔符可以乱填，一般情况下都用的是'#'
}
n=cnt;
for(int i=0;i<=n;i++){
	if(i<R) len[i]=min(2*C-i>=0?len[2*C-i]:0,R-i-1);
        //当黄框不超过r时，他就等于i'的len，否则从r开始枚举。
        //注意由于我len[1]设定为1所以i+len[i]实际上指到的是回文串右端点右边的点，所以要R-i-1
	else len[i]=1;		
	for(;i+len[i]<=n&&i-len[i]>=0&&s[i+len[i]]==s[i-len[i]];len[i]++);
        //一行的暴力向右推
	if(i+len[i]>R) R=i+len[i],C=i;
        //更新R,C
	ans=max(len[i],ans);
}