回文串

特点

回文串有如下特点或者理解：

• 判断回文串时，从回文串中间的“中心”向两边扩展。即仅当两头的字母相同时，回文串向外扩展一位。复杂度是线性的
• 回文串需要分奇数长度的和偶数长度。区别在于扩展的起点，奇数是从一个字符开始，偶数是两个字符
• 对于某一个扩展“中心”，以此为中心的回文串个数=以此为中心的最长回文串臂长 + 1。臂长指回文串的扩展次数。因为每一次扩展都会产生一个新的相同中心的回文串，再加上一开始的中心也是回文串，总共 n + 1 个

朴素算法

思想是依次遍历字符串每一个位置，从这个位置尝试扩展。从而找到所有回文串。

时间复杂度 $O(n^2)$。空间复杂度和要找的回文串的个数一致。（即找最长的串那便是 $O(1)$，找所有的串则 $O(n)$）

Manacher

已经实现。后续等差不多忘了再补上。

参考 Manacher - OI Wiki 谢谢喵。

• 对偶回文串的处理有许多要注意的地方。具体可以看力扣提交记录。
  • 偶数串从长度为 0 开始扩展。而不像奇数串一样从 1 开始。这是为了避免从 2 开始扩展时检验起始串的两个字符是否相同的特判
  • 偶数串的中心下标取在靠后的一个位置上。这样在一开始 i = 0 时跳过偶数串。