BZOJ2532 | CERC2010 Casting Spells

首先跑马拉车。

然后对于每个位置 i 我们求出他的回文对称半径 r_i 。比如说图上假设 i 是回文子串的中心(如果是偶数长度那就是中心的右侧),然后红色位置是子串的右末端,那么 r_i 就是:

然后有了 r_i 之后我们考虑合法的串长什么样子:

于是我们的任务就是找到满足以下条件的 j

  •  j+r_j \geqslant i
  •  j \geqslant i-\frac{r_i}{2}

然后就可以了。那么这里有一个 O(n \log n) 的搞法:从左到右枚举 i ,并同时维护两个集合:一个是当前所有满足条件 [1] 的 j 的位置集合,这个集合以 r_j+j 排序,并记录每个 r_j+j 对应的 j

另一个集合维护所有当前的合法位置 j ,并按照 j 排序。

每次扫到一个 i 只需先清空位置集合所有 r_j+j < ir_j+j 和合法集合对应的 j

然后求合法集合里 i - \frac{r_i}{2} 的后继即可。