字符串算法_Manacher

马拉车算法已经在

写过了。
这次只简单记录一下思路。

由 提到
字符串很多的算法是dp
而 Manacher 是利用回文的对称性来加速的。
假设已经算好的为 i 它的回文长度为 R
因为算法是从左到右的。所以 i-R 范围内肯定也是已经算好的了。
所以就可以加速度 i+R 范围的了 他的回文长度就等于对称的

注：原文 https://oi-wiki.org/string/manacher/