rin's

Manacher实例

作者: rin
时间: July 18, 2020
分类: 未分类
评论

[前坑](https://lo-li.net/1311-manacher-%E7%AE%97%E6%B3%95%E6%B1%82%E6%9C%80%E9%95%BF%E5%9B%9E%E6%96%87%E5%AD%90%E4%B8%B2.html)

![manacher2.png](https://static.lo-li.net/typecho/2020/07/2154660342.png)
符号说明：
* `i`为字符串中的下标，`S`是预处理后的字符串
* `P[i]`代表以`i`为中心（含）的地方，回文的半径长度。例如`P[1]=1`意为以`'#'`为中心的最长回文子串为`"#"`，半径长度为1；同样，`P[16]=4`意为以`'x'`为中心的最长回文子串`"#p#x#p#"`的半径`"#p#x"/"x#p#"`的长度4
* `id`代表当前已知的最长回文子串的中点；`mx`代表该子串的半径长度+1
* 带圈数字代表步骤

①、起始状态，`i=0,mx=0,id=0`
此时`i=1 >= mx=0`，即此位置已经超过了已知的最长回文范围（因为才开始嘛），同时也能确定`P[1]=至少=1`。
因此现在需要以`i=1`为中心，从其半径范围外两边开始逐一比对。（两边就是`i±P[i]`）
发现`'$'≠'a'`，扩展不下去了便停止，更新`id=1,mx=id+P[id]=1+1=2`

②、`i=2,mx=2,id=1`
此时`i=2 >= mx=2`，同样超过了已知的最长回文范围（注意`mx`是边界+1），同理能确定`P[2]=至少=1`。
继续扩展发现`'#'='#'`，则`P[2]++`，再继续无法扩展`$≠b`。
更新`id=2,mx=id+P[id]=2+2=4`

③、`i=3,mx=4,id=2`
此时`i < mx`了，说明`i`在**已知最长的回文子串（id=2的那个）**的势力范围内了。那么根据对称性，`i=3`在前面就有一个“分身”`j=2*id-i=1`
现在想求的`P[i]`就和`P[j]`有一种关系：`P[i]`=**可能**=`P[j]`，那么此时以`i`为中心的回文子串最右的下标就**有可能**扩展到`i+P[i]-1`，例如此时：
![manacher1.png](https://static.lo-li.net/typecho/2020/07/3248822752.png)
`i+P[i]-1=3+1-1=3 < mx=4`，`3`仍处在**能保证对称的<span style="background-color:#ffe699">势力范围内</span>**，那么上面的“可能”变成“一定”。
（当然现在串还太短效果不是很明显，可以参考后面的⑥；同时“不可能”的情况请参考文末）
④、⑤同理
⑥、`i=6,mx=10,id=5`
`P[6]=P[4]=2`，现在能从下标`6-2=4`和`6+2=8`的位置开始对比，而对称区域内的都不用再比了。所以就利用了已知的信息跳过了很多次对比。
然后`'b'≠'a'`停止，`6+2=8 < mx=10`，说明仍然处于最长的那个子串内部，所以不更新`mx,id`
……
如此便能算出所有的`P[i]`并且能得到最长的长度。

------------
“不可能”的情况
换一个例子
![manacher3.png](https://static.lo-li.net/typecho/2020/07/31183235.png)
此时`i=11,id=8,mx=14`
根据预判，`P[11]=P[5]=5`。但是下标`11+5=16 >= mx=14`，预判超过了**能保证对称**的部分，于是剩余的部分`14,15`就要和`8,7`暴力对比。