$Manacher$ 算法总结

今天学习了一下这个算法，做了几道题稍微找到了点感觉，过来写一下学习记录。

$Manacher$ 算法并不难理解，就是利用回文串对称的性质，将我们求解回文串的时间复杂度降至 $O(n)$ 。

这里总结一下几个性质和需要注意的点位。

性质

• 一个串中，本质不同的回文串最多有 $n$ 个，由算法过程中 $mx$ 最多更新 $n$ 次可以得到。
• 对于一个字符 $s_i$ ，以它为中心的回文串最大长度为 $p_i-1$ ，个数为 $p_i/2$ 。

注意点/小技巧

• 计算串的相交时，无论是奇回文串还是偶回文串，我们都可以将它们的端点放在我们加入的特殊字符处。这样计算时，我们只需要关注这些位置即可。