解题思路

思路

题目只统计奇长回文子串。若以某个位置为中心的最大奇回文半径为 $r$，那么该中心恰好贡献长度 $1,3,\ldots,2r-1$ 的回文各一个。因此只要求出每个中心的最大半径，就能从大到小统计每种长度的出现次数。

做法

子任务 1

枚举每个回文中心并向两侧扩展，把发现的所有奇回文长度加入数组。降序排序后取前 $K$ 个；若数量不足则输出 $-1$。

满分做法

用 Manacher 算法在线性时间内求出所有奇回文半径。对每个半径 $r$，将对应的最大长度 $2r-1$ 的计数加一。

从不超过 $n$ 的最大奇数长度开始，每次减少 $2$。用后缀累加值表示最大长度至少为当前长度的中心数；这也恰好是当前长度回文的数量。取尚需的前 $K$ 个中的尽可能多个，用快速幂计算当前长度的贡献，再继续处理下一个奇数长度。

正确性说明

Manacher 算法给出每个中心的精确最大奇回文半径。半径为 $r$ 的中心对每个不超过 $2r-1$ 的正奇数长度各贡献一个回文，所以对最大长度计数做降序后缀和，得到的正是每个长度的真实出现次数。按长度从大到小取满 $K$ 个，与将所有和谐小群体排序后取前 $K$ 个完全等价。快速幂只改变乘法次序，不改变模意义下的乘积。

复杂度

子任务 1 的时间复杂度为 $O(n^2+n^2\log n)$，空间复杂度为 $O(n^2)$。满分做法的时间复杂度为 $O(n+\log K)$，空间复杂度为 $O(n)$。