# Manacher算法

# 跟kmp一样,每年大厂必考的一道题.又频繁又噩梦.

manacher是一个加速回文的算法,暴力回文算法复杂度是O(N^2),manacher可以做到O(N).神奇

最长回文子串,子串,一定是连续的.

# 暴力算法

我们遍历字符串每个位置,然后i-1判断是否等于i+1位置,如果等,那就i-2是否等于i+2,一直下去,记录每个i位置最大的回文子串长度.

但是我们发现,有个问题,偶数的时候,我们找不到,是在虚轴上的时候,才能找到,但是我们不会遍历到这个虚轴,怎么办.

我们给他加工下,每个字符中间用#包起来,例如12321变成#1#2#3#2#1#,这样,不管是真实字符,还是虚轴,我们都会遍历到.那么这个字符一定要用#吗?还是任意都行?我们观察下会发现,真实字符,只会和真实字符比,#只会和#比,所以,是什么都行.

# Manacher算法核心

理解回文直径和回文半径,就是指 i位置,每个位置的回文直径,半径

例如,abc12321def ,对于3来说,直径就是5,半径是3.当然了,经过我们#的处理,任何串都是奇数,例如1221,#1#2#2#1#,
记录一个回文半径数组,par[],
理解所有中心的回文最右边界R，和取得R时的中心点C

举个例子,就是说一个串,任何位置,只要回文串最右边界推得更往右了,就用R抓住这个位置,同时R变的时候,记录C,C是哪个位置让他推出去的,两个变量是伴生的,当然了这个操作是基于那个加工串做的,就是###那个,R一开始就是在-1位置.
理解 L…(i`)…C…(i)…R 的结构，以及根据i’回文长度进行的状况划分,每一种情况划分，都可以加速求解i回文半径的过程
1. i没被R罩住,这种没优化
  1. 例如R在-1时候,我搞到0位置,不进行任何优化,因为我还没看过,就暴力扩.
2. i被R罩住了,这种有优化
  1. i'扩的范围,彻底在LR,范围内,
    
    例如:注意这个是带#的但是我没写,太乱了
```
ab[cdc]ks t skcdcda
L   i'    C    i  R
```
    看上面这个,i'的范围,完全在LR范围内.这种情况,我不用扩了,i位置跟i'一模一样.
  2. i'的范围,在LR范围之外
    
    举个例子:
```
(ab [ cdedc ba)t s tabcdedc ] f
    L   i'L'     C    R'i   R    
    {  甲  }          {  乙  }
```
    看上面这个,i'位置,超过L了,
    
    首先证明,L~L'肯定是回文,因为他们是i'对称.
    
    然后,R'~R也肯定是回文,因为他们和甲相对C是回文.
    
    那甲左右,假设是ab,乙左右是xy,因为i'的范围超过L,那说明a==b,因为相对C回文,所以,b == x,
    
    那么为什么LR范围不包含a和y,因为a和y一定不相等,也就是a == x 但是 a ≠ y 所以 x ≠ y,
    
    也就是说,i位置的范围,仅仅是R'~R,不可能更大了
  3. i'的左范围,正好压中了L,
    
    举个例子
```
  x a b c b a s t s a b c b a s
    (   i'  )				{				}
    L       L'  C   R'  i   R
```
    看上面这个,我们知道i位置,至少是R'~R我是不用验证的,但是有没有可能突破了,不知道,得去验证,例如上面这个,就可以突破到s

# 代码解析

← KMP算法蓄水池算法 →