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)  符号说明： * `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`，例如此时：  `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]`并且能得到最长的长度。 ------------ “不可能”的情况 换一个例子  此时`i=11,id=8,mx=14` 根据预判，`P[11]=P[5]=5`。但是下标`11+5=16 >= mx=14`，预判超过了**能保证对称**的部分，于是剩余的部分`14,15`就要和`8,7`暴力对比。 标签: none