2020牛客多校第二场A-All with Pairs


\(对每个s_i的前缀s_{i, 1…j}进行与所有后缀比较,相同的次数记为res_{i,j},此处可以用哈希进行比较 \)

\(因为要取最大前缀,所以要用kmp求出next数组后res_{i,next[j]} -= res_{i, j},注意一下下标的偏移 \)

\(答案就是\Sigma_{i=1}^n\Sigma_{j=1}^{len_i}j^2res_{i,j} \)


 

发表评论