Y252 单词频率

题目大意

给定 \(n\) 个单词，求每个单词作为子串在所有单词中一共出现过多少次。

首先我们注意到，字符串 \(s\) 是另一个字符串 \(t\) 的子串等价于 \(s\) 是 \(t\) 的一个前缀的后缀。并且 \(s\) 唯一对应该前缀和后缀。

我们先通过字典树求出每个字符串是多少个字符串的前缀，记数量为 \(cnt_i\)，则该字符串就会对其所有后缀产生 \(cnt_i\) 的贡献。

对其所有后缀的贡献，我们考虑在AC自动机预处理时记录所有节点访问的顺序（也就是bfs序），接着按 bfs 序反着计算i对fail[i]的贡献，这和拓扑排序是等价的。