不会写的做法，不保证正确：

首先发现前缀后缀是否相等可以直接哈希判断，那么这个问题就化为了求 $s_{i+1\sim n-i}$ 的 border。

我并没有发现这个东西可以类 KMP 势能分析均摊 $\mathcal O(1)$ 计算的性质，但是我学过一点点后缀数组，知道 LCP（最长公共前缀）的一个性质：

$$\forall 1\le i\lt j\lt k\le n,\text{LCP}(sa_i,sa_k)=\min\{\text{LCP}(sa_i,sa_j),\text{LCP}(sa_j,sa_k)\}$$

把 $\gt \lceil \frac{n}{2} \rceil$ 的 $sa$ 值标记一下，从前往后递推一遍，得到每个 $sa_i$ 前面第一个被标记过的 $sa$，用 RMQ 求值即可。

时间复杂度 $\mathcal O(n\log n)$，后缀数组常数卡小点估计能过，但一点也不精妙。

定义 $f_i$ 表示 $s_{i+1\sim n-i}$ 的最长不重叠公共前后缀长度。

当我们从大到小枚举 $i$，显然有 $f_i\le f_{i+1}+2$。

从洛谷题解搬的一张图：

那么我们不妨令 $f_i=f_{i+1}+2$，用哈希判合法性，不合法时暴力往前跳。

和 KMP 类似，势能总和为 $n$，那么总的时间复杂度就是 $\mathcal O(n)$。

很有启发的一道题，从中认识到，不能忽视原题中某些「显而易见」的性质，认真分析，它们有可能就是通往正解的钥匙。