思路
设字符串 $s$ 的长度为 $n$。
我们考虑每一个位置上的字符的贡献即可。对于 $s_i$,我们假设 $s_i$ 两旁最靠近 $s_i$ 且和 $s_i$ 相同的字符为 $s_{l-1}$ 和 $s_{r+1}$(如果不存在 $s_{l-1}$ 则 $l=1$,如果不存在 $s_{r+1}$ 则 $r=n$)。
那么通过乘法原理可以得到 $s_i$ 的贡献就是 $(i-l+1)\times (r-i+1)-1$。这里我们可以看成是在 $[l,i]$ 中选择若干个且在 $[i,r]$ 中选择若干个组成字符串 $t$,则在 $t$ 中 $s_i$ 的数量就只有一个了。$-1$ 是因为我们考虑了两次只选择 $s_i$ 一个字符串组成字串的情况,要减去 $1$。
那么怎么样预处理呢?从前往后扫一遍,从后往前扫一遍,并且在每一个位置记录 $pre_i$ 和 $nxt_i$ 即可。