Manacher是一个求出一个字符串中所有回文子串的利器。
记录方法
首先我们发现一个问题，一个长为 \(S\) 的字符串一共有 \(S^2\) 个子串，所以记录回文子串时不可能记录左右端点。如何解决呢？根据回文串的特点，我们发现，一个回文串，将它的两端各删去一个字符，那么它还是一个回文串。所以我们可以记录下每一个回文串的中心点以及回文串的“半径” \(a_i\) ，这样记录的问题解决了，接下来就到如何快速求解了。
过程
在Manacher中，我们需要维护一个 \(l\) 和 \(r\) ，表示当前右端点最靠右的回文串是哪个。设当前枚举到的中心点为 \(i\) ，之前的所有点的 \(a\) 已计算完毕，分两种情况讨论：
\(i>r\)
此时我们不能从前面计算到的数据求出当前点的 \(a_i\) ，只能暴力扩展半径到不能再扩展为止。
\(i\le r\)
此时我们可以从当前的这个回文串中找到 \(i\) 的对应点 \(j=l+(r-i)\) ，之后我们在大部分情况下可以将 \(a_j\) 赋值 \(a_i\)。但是考虑到可能 \(j-a_j\) 比 \(l\) 小，不能保证 \(r\) ~ \(i+a_i\) 和 \(l\) ~ \(j-a_j\) （这个是倒过来的）相同，所以在赋值时将 \(a_j\) 与 \(r-i\) 取 \(min\) ，之后再暴力扩展。
计算完一个点的 \(a\) 后，要记得更新 \(l\) 和 \(r\)。
初始值可以设为 \(l=0,r=-1\) 。
技巧
等等，上面讲的好像是只能算奇数长度的回文子串，那偶数的怎么办？
其实用上面的方法再推一推就可以找到计算偶数的方法了。但是有另一个技巧，可以在原字符串中，每两个字符中间插入一个不在原字符集中的字符（例如‘#’），这样就可以一遍算出所有的回文子串。
如果怕在枚举时边界不好控制，也可以在字符串两端加不一样的特殊字符。
标签：子串,记录,一个,Manacher,笔记,学习,字符串,回文 From： https://www.cnblogs.com/Cyanwind/p/18172620