求以指定索引为中心的最长奇回文子串长度的高效解法问询

问题描述 #

给定仅由小写字符组成的字符串S和Q个查询，每个查询给出一个1-based索引i，需找出以i为中心的最长奇数长度回文子串的长度。

约束条件 #

• 1 ≤ |S|、Q ≤ 1e5
• 1 ≤ i ≤ |S|

输入输出格式 #

• 输入：第一个参数为字符串S，第二个参数为查询索引数组B
• 输出：返回对应每个查询结果的整数数组

当然有更优解法，暴力枚举每个查询的回文扩展时间复杂度为O(n*Q)，对于1e5的规模来说会直接超时，必须使用线性时间预处理+O(1)查询的方案，这里最适合的是Manacher算法（针对奇数长度回文的简化实现即可）。

核心解法：Manacher算法（针对奇数长度回文） #

Manacher算法通过利用回文的对称性，在线性时间内预处理出每个位置作为中心的最长奇数长度回文的关键信息，之后每个查询可以直接给出结果。

预处理步骤

1. 定义数组p，其中p[i]表示以原字符串S中第i个字符（1-based）为中心的最长奇数回文的半径（例如：若中心i的回文长度为5，则半径为3，回文长度公式为2*p[i]-1）。
2. 维护两个变量：
   • max_right：当前已知所有回文子串的最右端位置
   • center：对应max_right的回文子串中心
3. 遍历字符串每个位置i（从1到n）：
   • 若i在max_right范围内，利用对称性初始化p[i] = min(p[2*center - i], max_right - i + 1)
   • 尝试向两侧扩展：当i-p[i] >=1且i+p[i] <=n且S[i-p[i]] == S[i+p[i]]时，p[i] +=1
   • 若扩展后的回文右端i+p[i]-1超过max_right，更新max_right = i+p[i]-1和center = i
4. 预处理完成后，每个查询索引i对应的结果就是2*p[i]-1。

时间复杂度

• 预处理：O(n)，因为扩展操作只会让max_right单调递增，总扩展次数不超过n次
• 查询：O(Q)，每个查询直接取数组值即可

整体时间复杂度为O(n+Q)，完全满足1e5的约束要求。

内容的提问来源于stack exchange，提问作者lemn09